Aportaciò a la detecció de simetries en imatges amb projecció ortogràfica

Abstract

El mètode de detecció de simetria local de reflexió que es presenta, pretén ser una aportació més a la recerca en visió per computador i la robòtica. Com és sabut haches camps d'aplicació impliquen considerar el temps de processament com un paràmetre bàsic. Així doncs, en aquesta tesi no ens conformem en obtenir un algorisme eficient de detecció de simetria si no que es planteja millorar el temps de processame nt a partir de l'obtenció de metodologies i algorismes que tinguin la qualitat de permetre una fácil implantació del processament en paral· lel així com de la implementació de processadors específics.<br/>El mètode de detecció de simetria es basa en les contribucions a la simetria de les parelles de segments rectilinis de la imatge. Aquesta aproximació permet una reducció considerable de la complexitat, de la mateixa manera que altres autors utilitzen reduccions basades en diferents agrupacions de punts de contorn, com ara segments d'arcs, b-splines etc. El mètode, així concebut, serà aplicable en imatges on les línies rectes siguin predominats com és el cas de construccions artificials i entorns estructurats.<br/>Tot i que l'anterior restricció és important, és adequada per al tipus d'aplicacions que hem exposat anteriorment i ens permet obtenir un mètode de detecció contributiu, a partir de l'acumulació de contribucions locals a la simetria de les parelles de segments rectilinis de la imatge. Es tracta doncs d'un mètode basat en un anàlisi local que mostra els avantatges d'aquesta aproximació mentre que pel fet de tractar-se d'un mètode contributiu millora els dos principals inconvenients de l'aproximació local, és a dir, la sensibilitat al soroll i la inestabilitat, la qual cosa representa una aportació a la superació del dilema "anàlisi local versus anàlisi global".<br/>El mètode es composa de quatre etapes:<br/>- Obtenció de la llista de segments rectilinis de la imatge<br/>- Obtenció dels segments de contribució a la simetria<br/>- Càlcul del mapa d'acumulació dels segments de contribució<br/>- Extracció d'eixos locals de simetria<br/>Una característica que distingeix el mètode és que proporciona l'abast de la simetria, és a dir, la llargada dels eixos de simetria, precisant-ne els punts inicial i final. <br/>Per altra banda la característica contributiva del mètode proposat, ha permès detectar els eixos de simetria local amb una ponderació associada segons la seva importància. <br/>D'aquesta forma s'evita el processat d'alt nivell posterior per tal de determinar els eixos més significatius, necessari en la majoria de mètodes basat en l'aproximació local. <br/>Respecta la millora del temps de processat i donada la complexitat i extensió del problema de la detecció de simetria, s'ha fet un primer esforç en una de les etapes del mètode de més cost de computació. Concretament s'ha accelerat un procés que forma part del càlcul del mapa d'acumulació esmentat anteriorment, consistent en l'obtenció dels píxels que aproximen, en el pla discret, un segment rectilini especificat per els seus punts inicial i finals. Aquesta millora s'ha obtingut mitjançant un algorisme paral· lel que presenta com avantatges més rellevants: la simplicitat, eficiència i que permet un directa implementació d'un processador dedicat. <br/>Per l'altra banda, amb el mateix objectiu de millorar el temps de processament i en base a l'algorisme anterior, s'ha dissenyat un processador paral· lel dedicat que té la capacitat d'obtenir i emmagatzemar simultàniament, en una matriu de registres, el conjunt de píxels que aproximen, en el pla discret, un segment rectilini caracteritzat per els seus punts inicial i final. Una característica molt remarcable del processador és que obté i registra els píxels anteriors en un únic període de rellotge.<br/>Finalment per tal de conèixer el paràmetres referents a la seva viabilitat i prestacions, s'ha obtingut, mitjançant la simulació, una versió reduïda amb tecnologia d'alta escala d'integració VLSI en un únic circuit. El disseny obtingut ha mostrat la capacitat de processar17,2 Mega Segments/seg, en el pitjor del casos, mentre que en les condicions més favorables es capaç de processar 57,3 Mega segments/segon.

The method of reflection local symmetry detection presented aims to be a new approach to the research in vision computer and robotics. As we know them, these fields of application imply to consider the processing time as a basic parameter. In this way, in this thesis we shall obtain an efficient algorithm for symmetry detection and, moreover, we will try to improve the processing time with methodologies and algorithms that will be able to embed easily in parallel architectures and the implementation of specific processors.<br/>The symmetry detection method is based in symmetry contributions from the straight segments in the image. This approximation permits a considerable reduction in the complexity in the same way that other authors use reductions based in different grouping of contour points, such as arcs, b-splines, etc. The method conceived like this will be applicable in images where straight lines are predominant like in the case of artificial buildings and structured environments.<br/>Although the above restriction is important, it is suitable for all kinds of applications that we have exposed previously and it allows us to obtain a contributive detection method from the accumulation of local contribution of symmetry in pairs of straight segments in the image. Thus, it is a method based in the local analysis that shows the advantages of this approach while it improves the two main disadvantages of local approximation because it is a contributive method. These drawbacks are the sensibility to noise and instability which represent a novel approach to the overcoming of the "local analysis versus global analysis" dilemma.<br/>Four steps compose the method: <br/>- To obtain the straight segments list in the image<br/>- To obtain the symmetry contribution segments<br/>- To calculate an accumulation map of contribution segments<br/>- To extract the local symmetry axes.<br/>A distinctive feature is that the method yields the symmetry range, that is, the length of symmetry axes, with precise position of initial and final points.<br/>On the other hand, the contributive feature of the proposed method has allowed us to detect the local symmetry axes with an associated weight to their importance. That avoids the posterior high level processing in order to determine the more significative axes needed in most of the approaches based in local approximation. With respect to the improvement of processing time, and given the complexity and extension of the symmetry detection problem, an initial effort has been made in one of the stages of higher computational cost in the method. Specifically, a process in the calculation of the accumulation map has been accelerated, consistently in the achieving of pixels that form, in the discrete plane, a straight segment specified for its initial and final points. This improvement has been obtained with a parallel algorithm that presents more relevant advantages: simplicity, efficiency and it allows a direct implementation with a dedicated processor.<br/>Furthermore, with the same objective of processing time improvement and in basis to the above algorithm, a dedicated parallel processor has been designed with the capability to obtain and store simultaneously, in an array of registers, the set of pixels that approximate, in the discrete plane, a straight segment characterised by its initial and final points. A very remarkable feature of the processor is to obtain and store those pixels in a unique clock period.<br/>Finally, in order to know the parameters concerning its viability and performance, a simulated reduced version with VLSI (very large scale integration) technology in a unique circuit has been achieved. The obtained design has shown the capability of processing 17.2 million segments per second in the worst case, while in the most favourable conditions it is able to process up to 57.3 million segments per second.