Algoritmos de detecção de linhas são usados em muitos campos de aplicação, tais como visão computacional e automação como base para análises mais complexas. Por exemplo, a informação de linha pode ser usada como dado de entrada para algoritmos de detecção de objetos ou mesmo para a estimativa da orientação espacial de robôs aéreos. Uma das formas de detectar linhas é através do uso de um processo de filtragem não linear chamado deWide Line Detector (WLD). Esse algoritmo é eficaz na marcação de pixels de linha em imagens em tons de cinza, separando linhas claras ou linhas escuras. Contudo, os algoritmos de detecção de linha não estão normalmente preocupados com a estimativa de largura local individual associada a um pixel. Se disponível, tal informação poderia ser explorada por algoritmos de visão computacional. Além do mais, a informação de cor também é extensivamente usada em visão computacional como um discriminante de objetos, mas o WLD não a usa. Neste Trabalho, nós propusemos a extensão do WLD para imagens em cores. Nós também desenvolvemos um novo kernel monotonicamente crescente que é mais eficiente e mais robusto para detectar linhas do que que os kernels monotonicamente decrescentes usados pelo WLD. Por fim, desenvolvemos uma maneira de obter uma estimativa de largura de linha partindo da densidade local associada a similaridade entre pixels, revertendo o processo usado pelo WLD para estimar qual kernel deve ser usado. Diversos experimentos foram realizados com o método proposto considerando diferentes parâmetros, além da comparação com o WLD tradicional, para analizar a eficácia do método. / Line detection algorithms are used by many application fields, such as computer vision and automation, as a basis for more complex analysis. For instance, line information can be used as input to object detection algorithms or even attitude estimation in flying robots. One way to detect lines is to use an isotropic nonlinear filtering procedure called the Wide Line Detector (WLD). This algorithm is effective to highlight the line pixels in gray scale images, separating dark or bright lines. However, line detection algorithms are not normally concerned with the pixel-wise estimation of thickness. If available, such information could be further explored by computer vision algorithms. Furthermore, color is extensively used in computer vision as an object discriminant, but not by the WLD. In this work, we propose the extension of the WLD to color images. We also develop a method that allows the estimation of the line width locally using only the density information and no border or center line information. Finally, we develop a new monotonically increasing kernel that is more efficient and yet effective to detect lines than the monotonically decreasing kernels used by the WLD. Finally, we devise a way ro obtain the wideline thickness from the density estimate obtained from the similarity between pixels, reverting the process used by the WLD to determine which kernel should be used. We perform several experiments with the proposed method, considering different parameters, and comparing it to the traditional WLD algorithm to assess the effectiveness of the method.

A iluminação indireta é capaz de elevar consideravelmente a qualidade visual de cenas renderizadas, mas é também uma operação custosa. Por este motivo, há muito esforço de pesquisa voltado para a renderização de iluminação indireta em tempo real. Apesar de atualmente existirem técnicas poderosas para a iluminação indireta em tempo real, elas fornecem ao artista apenas um controle grosseiro do equilíbrio entre qualidade e desempenho. Nós propomos uma Malha de Luzes Virtuais para calcular a iluminação indireta difusa numa cena, inspirados pelo uso de outras malhas auxiliares, como Malhas de Navegação e Malhas de Colisão. Uma Malha de Luzes Virtuais (MLV) é uma malha simplificada de luzes poligonais usadas para aproximar a luz refletida pela geometria real. Juntamente com a MLV, nós projetamos uma estrutura de dados de aceleração para atingir um desempenho eficiente com iluminação indireta usando uma MLV complexa. O uso da MLV apresenta algumas características vantajosas: maior controle artístico dos atributos da iluminação indireta; a possibilidade de integração com técnicas existentes como animação esquelética e geração procedural; e integração simples com ferramentas e processos de produção de arte existentes. Nossos resultados experimentais mostram que a iluminação indireta controlada por artistas é uma alternativa viável a métodos existentes. / Indirect illumination on a rendered scene can add a great deal to its visual quality, but it is also a costly operation. Therefore, a lot of research targets how to render indirect illumination in real-time. While powerful techniques for real-time indirect illumination currently exist, they provide only coarse-grained artistic control over the trade-off between quality and speed. We propose a Virtual Light Mesh to compute the scene’s diffuse indirect illumination, inspired by the use of other current auxiliary meshes such as Navigation Meshes and Collision Meshes. A Virtual Light Mesh (VLM) is a simplified mesh of polygonal lights used to approximate the light bounced by the real geometry. Together with the VLM, we design an acceleration data structure for efficient indirect illumination performance with a complex VLM. The use of VLM presents some positive properties: greater artistic control of the indirect illumination characteristics; the possibility of integration with existing techniques such as skeletal animation and procedural generation; and simple integration into existing asset production tools and pipelines. Our experimental results show that artist controlled indirect illumination is a viable alternative to existing methods.

A simulação de cores corresponde à essência do processo de síntese de imagens realistas. Em se tratando de minerais, a presença de uma dada impureza, ou uma variação de sua concentração, pode fazer com que alguns materiais sofram alterações dramáticas em suas cores. Por exemplo, enquanto o quartzo puro é transparente, a ametista é um tipo violeta de quartzo, cuja cor é determinada pela presença de traços de ferro. A quantidade de ferro define o matiz percebido. A cor apresentada por um mineral pode ser determinada com base no seu espectro de absorção. No entanto, a definição de todas as variações possíveis é impraticável e, portanto, tal informação está disponível apenas para um subconjunto dos minerais existentes. Esta dissertação apresenta uma proposta para estimar a cor de ágatas, bem como para simular as cores de ágatas sintéticas (inexistentes). A abordagem utilizada baseia-se nos fundamentos da teoria quântica, e parte de uma descrição da molécula de sílica que se deseja simular. À esta, pode-se adicionar quantidades diferentes de impurezas e alterar o número de átomos incluídos na simulação. O resultado obtido é o espectro de absorção do mineral, que pode então ser utilizado para determinar a cor da ágata com a composição desejada. Embora uma simulação detalhada de todo o processo seja uma tarefa computacionalmente extremamente cara, esta dissertação apresenta alguns resultados que corroboram com a correção da solução proposta. Também é apresentada uma técnica independente que pode ser utilizada para definir um volume de ágata com base em uma imagem 2D. / Color simulation is the essence of realistic image synthesis. In the case of minerals, the presence of a given impurity, or a variation of its concentration, can cause some materials to experience dramatic changes in color. For instance, while pure quartz is transparent, amethyst is a violet type of quartz, whose color is determined by the presence of traces of iron. The amount of iron defines the perceived hue. The color presented by a mineral can be determined based on its absorption spectrum. However, defining all possible variations is impractical and, therefore, such information is available only for a subset of the existing minerals. This thesis presents an approach for simulating the colors of existent agates, as well as for predicting the colors for (non-existent) synthetic ones. The approach is based on the fundamentals of quantum theory, and starts with the description of the silica molecule one wants to simulate. One can add different amounts of impurities, and alter the number of atoms included in the simulation. The obtained result is the absorption spectra of the mineral, which can then be used for determining the color of the agate with the desired composition. Although a detailed simulation of the entire process is extremely computationally-expensive, the thesis presents some results that corroborate the correctness of the proposed solution. It also introduces a standalone technique for defining agate volumes based on 2D images of agates.

Com o constante crescimento tecnológico, é bastante comum deparar-se com um display público em lugares de grande concentração de pessoas, como aeroportos e cinemas. Apesar de possuírem informações úteis, esses displays poderiam ser melhor aproveitados se fossem interativos. Baseando-se em pesquisas sobre a interação com displays grandes e as características próprias de um display colocado em um espaço público, busca-se uma maneira de interação que seja adequada a esse tipo de situação. O presente trabalho introduz um método de interação por gestos sem necessitar que o usuário interagente segure ou tenha nele acoplado qualquer dispositivo ao interagir com um display público. Para realizar as tarefas que deseja, o usuário só precisa posicionar-se frente ao display e interagir com as informações na tela com suas mãos. São suportados gestos para navegação, seleção e manipulação de objetos, bem como para transladar a tela de visualização e ampliá-la ou diminui-la. O sistema proposto é construído de forma que possa funcionar em aplicações diferentes sem um grande custo de implantação. Para isso, é utilizado um sistema do tipo cliente-servidor que integra a aplicação que contém as informações de interesse do usuário e a que interpreta os seus gestos. É utilizado o Microsoft Kinect para a leitura dos movimentos do usuário e um pós-processamento de imagens é realizado de modo a detectar se as mãos do usuário se encontram abertas os fechadas. Após, essa informação é interpretada por uma máquina de estados que identifica o que o usuário está querendo executar na aplicação cliente. Afim de avaliar o quão robusto o sistema se portaria em um ambiente público real, são avaliados critérios que poderiam interferir na tarefa interativa, como a diferença de luminosidade do ambiente e a presença de mais pessoas no mesmo local de interação. Foram desenvolvidas três aplicações a título de estudo de caso e cada uma delas foi avaliada de forma diferente, sendo uma delas utiliza para fins de avaliação formal com usuários. Demonstrados os resultados da avaliação realizada, conclui-se que o sistema, apesar de não se portar corretamente em todas situações, tem potencial de uso desde que sejam contornadas suas deficiências, a maior parte das quais originária das próprias limitações inerentes ao Kinect. O sistema proposto funciona suficientemente bem para seleção e manipulação de objetos grandes e para aplicações baseadas em interação do tipo pan & zoom, como navegação em mapas, por exemplo, e não é influenciado por diferenças de iluminação ou presença de outras pessoas no ambiente. / With the constant technological growth, it is quite common to come across a public display in places with high concentration of people, such as airports and theaters. Although they provide useful information, these displays could be better employed if they were interactive. Based on research on topics of interaction with large displays and the characteristics of a display placed in a public space, a way of interaction that is suitable for this kind of situation is searched. This paper introduces a method of interaction by gestures without requiring that the interacting user take hold or have to him attached any device to interact with a public display. To accomplish the tasks he wants, he needs just to position himself in front of the display and to interact with the information on the screen with his hands. Gestures supported provide navigation, selection and manipulation of objects as well as to pan and zoom at the screen. The proposed system is constructed so that it works in different applications without a large installation cost. In order to achieve this, the system implements a client-server model application that is able to integrate the part that contains the useful information to the user and the one that interprets his gestures. The Microsoft Kinect is used for reading the user’s movements and techniques of image processing are performed to detect if the user’s hands are open or closed. After this information is obtained, it runs through a state machine that identifies what the user is trying to do in the application. In order to evaluate how robust the system is in a real public environment, some criteria that could interfere with the interactive task are evaluated, as the difference in brightness in the environment and the presence of another people in the same place of interaction. Three applications were developed as a case study and each one was evaluated differently, one of them being used for formal user evaluation. Given the results of the performed tasks, it is possible to conclude that the system, although not behaving correctly in all situations, has potential use if its difficulties are circumvented, most of which come from Kinect’s own inherent limitations. The proposed system works well enough for selection and manipulation of large objects and for use in applications based on pan & zoom, like those that supports map navigation, for example, and difference of ilumination or the presence of other persons on the environment does not interfere with the interaction process.

Melanoma é um tipo maligno de lesão de pele pigmentada, e atualmente está entre os tipos de câncer existentes mais perigosos. Entretanto, diferenciar casos malignos de benignos é uma tarefa difícil mesmo para experientes especialistas, e um sistema de diagnóstico auxiliado por computador pode ser uma ferramenta bastante útil. Normalmente, este sistema inicia por um pré-processamento da imagem, isto é, remoção de artefatos indesejados, como pelos, sardas ou efeitos de sombreamento. A seguir, o sistema executa uma etapa de segmentação, identificando as bordas da lesão. Por fim, baseando-se na área da imagem identificada como lesão, diversas feições são computadas e uma classificação é gerada. Neste tese, apresentada na forma de uma coleção de artigos publicados, nós apresentamos técnicas para automaticamente executar todos estes passos, resultando em um pré-diagnóstico para uma lesão de pele pigmentada baseado apenas em uma imagem convencional (uma simples fotografia). Nós testamos nossos métodos em bases de imagens públicas e atingimos melhores resultados de segmentação e classificação que os demais métodos presentes na literatura. / Melanoma is a type of malignant pigmented skin lesion, and currently is among the most dangerous existing cancers. However, differentiating malignant and benign cases is a hard task even for experienced specialists, and a computer-aided diagnosis system can be an useful tool. Usually, the system starts by pre-processing the image, i.e. removing undesired artifacts such as hair, freckles or shading effects. Next, the system performs a segmentation step to identify the lesion boundaries. Finally, based on the image area identified as lesion, several features are computed and a classification is provided. In this Thesis, presented as a collection of published papers, we detail approaches to automatically execute all these steps, resulting in a pre-diagnosis for a pigmented skin lesion based only in a standard camera image (i.e. a simple color photograph). We tested our methods on publicly available datasets and achieved better segmentation and classification results than methods previously proposed in the literature.

Esta dissertação apresenta um novo método para cálculo da pose da cabeça em imagens monoculares. Este cálculo é estimado no sistema de coordenadas da câmera, comparando as posições das características faciais específicas com as de múltiplas instâncias do modelo da face em 3D. Dada uma imagem de uma face humana, o método localiza inicialmente as características faciais, como nariz, olhos e boca. Estas últimas são detectadas e localizadas através de um modelo ativo de forma para faces. O algoritmo foi treinado sobre um conjunto de dados com diferentes poses de cabeça. Para cada face, obtemos um conjunto de pontos característicos no espaço de imagem 2D. Esses pontos são usados como referências na comparação com os respectivos pontos principais das múltiplas instâncias do nosso modelo de face em 3D projetado no espaço da imagem. Para obter a profundidade de cada ponto, usamos as restrições impostas pelo modelo 3D da face por exemplo, os olhos tem uma determinada profundidade em relação ao nariz. A pose da cabeça é estimada, minimizando o erro de comparação entre os pontos localizados numa instância do modelo 3D da face e os localizados na imagem. Nossos resultados preliminares são encorajadores e indicam que a nossa abordagem produz resultados mais precisos que os métodos disponíveis na literatura. / This dissertation presents a new method to accurately compute the head pose in mono cular images. The head pose is estimated in the camera coordinate system, by comparing the positions of specific facial features with the positions of these facial features in multiple instances of a prior 3D face model. Given an image containing a face, our method initially locates some facial features, such as nose, eyes, and mouth; these features are detected and located using an Adaptive Shape Model for faces , this algorithm was trained using on a data set with a variety of head poses. For each face, we obtain a collection of feature locations (i.e. points) in the 2D image space. These 2D feature locations are then used as references in the comparison with the respective feature locations of multiple instances of our 3D face model, projected on the same 2D image space. To obtain the depth of every feature point, we use the 3D spatial constraints imposed by our face model (i.e. eyes are at a certain depth with respect to the nose, and so on). The head pose is estimated by minimizing the comparison error between the 3D feature locations of the face in the image and a given instance of the face model (i.e. a geometrical transformation of the face model in the 3D camera space). Our preliminary experimental results are encouraging, and indicate that our approach can provide more accurate results than comparable methods available in the literature.

Um dos objetivos permanentes da Computação Gráfica é a representação fiel, e por consequência realista, da aparência de objetos e cenas sintetizadas. Para objetos e cenas do Reino Vegetal pode-se dizer que houve um grande avanço nos métodos para modelagem da forma e propriedades de reflexão de elementos individuais, como folhas, e de coleções de elementos, como árvores, vegetação em geral e florestas. Por outro lado, as técnicas para modelagem de padrões visuais presentes em muitos objetos naturais do Reino Vegetal, como listras de melancias ou padrões em folhas e flores, não tem recebido a mesma atenção. O presente trabalho tem por objetivos principais o estudo de técnicas de Computação Gráfica aplicáveis ao Reino Vegetal, principalmente explorar o modelo procedural Mosaico de Clones (MClone), desenvolvido em pesquisas anteriores, para a síntese de padrões visuais familiares do Reino Vegetal. Nossos resultados mostram que, neste contexto, um modelo procedural tem vantagens sobre outras técnicas, como, por exemplo, mapeamento de texturas, pois geralmente esses padrões são necessários em grande quantidade, e, ao menos para algumas plantas, com muitas variações geométricas, a atribuição de coordenadas de textura consistentes é um desafio. Nós mostramos resultados para frutos, cactus e pequenas folhagens decorativas, que confirmam a aplicabilidade do MClone para uma ampla gama de padrões do Reino Vegetal. / There has been a lot of progress in modeling and rendering elements of our Natural World for computer graphics tasks. In the Plant Kingdom, techniques for modeling the visual patterns presented in many natural objects (such as stripes on a watermelon or spots on flowers) have advanced far less than methods for modeling the shape and reflectance properties of individual or large collections of elements (such as leaves and trees). In this work we want to explore the procedural Clonal Mosaic Model (MClone), developed in previous research, for synthesis of many familiar visual patterns from the Plant Kingdom. Our results show that in this context a procedural model has advantages over other techniques such as texture mapping, since these patterns are often needed in large quantities, and at least for some plants, with many geometric variation, assigning consistent texture coordinates is a challenge. We show results for fruits, cactus, and small decorative plants, which confirm the applicability of the MClone model for synthesis of a large group of visual patterns in the Plant Kingdom.

Seleção é uma das quatro formas fundamentais de interação em mundos virtuais. É a habilidade de especificar objectos em ambientes virtuais para ações posteriores. A literatura é rica em técnicas de seleção imediata; no entanto, esta classe de técnicas está exposta a problemas de precisão, ambiguidade e complexidade de seleção. Os problemas mencionados podem ser abordados com técnicas de seleção por: refinamento prograssivo, que consiste na redução da quantia de objetos selecionáveis através de etapas de refinamento, até que o objeto desejado seja selecionado; ou níveis de precisão, que consiste em aumentar a precisão de apontamento através da manipulação de parametros do mapeamento controle para display, assim como na combinação de abordagens de apontamentio. Níveis de precisão é uma classe de técnicas de seleção que estamos propondo neste dissertação. Neste documento também apresentamos uma pesquisa com literatura relacionada a estas duas classes de técnicas de seleção. Adicionalmente, propomos as técnicas de seleção LOP-cursor e tela de desambiguação. A primeira conta com múltiplos níveis de precisão para proporcionar maior controle sobre a posição do cursor, enquanto a segunda usa a alta resolução de entrada proporcionada pela tela sensível ao toque de disposiiticos móveis para rapidamente desambiguar a seleção de um alvo entre centenas de outros objetos. Por fim, apresentamos a metáfora de um cursor com duas pernas, uma nova abordagem para apontar duas posições distintas simultaneamente. O cursor de duas pernas é projetado para rapidamente realizar tarefas compostas, como arrastar e soltar em uma área de trabalho. Avaliações com usuários mostram que nossas abordagens são promissoras, e que o espaço de design de técnicas utilizado dispoitivos móveis pode produzir inúmeras possibilidades. Os usuários foram capazes de selecionar alvos com 0:1 de tamanho angular visual com o LOP-cursor. Em um dos experimentos, a tela de desambiguação obteve a proporção de erro < 0:01 por tentativa de seleção. Por fim, ambas as técnicas foram mais rápidas que o tradicional ray-casting para seleção de objetos pequenos, sendo sempre preferidas pelos usuários. / Selection is one of the four fundamental forms of interaction in a virtual world. It is the ability of the user to specify objects in the virtual environment for subsequent actions. The literature is rich in immediate selection techniques; however, this class of technique is exposed to problems of selection accuracy, ambiguity and complexity. These issues can be addressed using techniques of selection by: progressive refinement, which consists of reducing the amount of selectable objects through refinement steps until the desired object is selected; or levels of precision, which consists of increasing accuracy of pointing by manipulating the control-to-display parameters as well as by the combination of pointing approaches. Levels of precision is a class of selection techniques we are proposing in this dissertation. We also present a survey that comprehends literature on these two classes of selection techniques. Furthermore, we propose the LOP-cursor and the disambiguation canvas selection techniques. The first rely on multiple levels of precision to achieve very high control over the cursor position, while the second uses the high resolution of input provided by a mobile device touchscreen to quickly disambiguate a selection among hundreds of objects. Finally, we present the two-legged cursor metaphor, a novel approach for simultaneously pointing of two distinct locations. The two-legged cursor is intended to be used to quickly perform composite tasks, such as drag and drop. User evaluation shows that our approaches are promising, and that the design space of techniques using mobile devices can lead to numerous possibilities. Users were able to select targets as little as 0:1 of visual angular size with LOP-cursor. In one of its evaluations, disambiguation canvas achieved an error rate < 0:01 per selection trial. Finally, Both techniques performed faster than ray-casting for small targets, and overall they were preferred by users.

Topografias da córnea consistem em medir a forma da córnea, que é um fator chave para a acuidade visual. O exame é usado, por exemplo, na detecção de ceratocone, ajuste personalizado de lentes de contato, e pre e pós procedimentos associados com cirurgias refrativas e transplante de córnea. Esta dissertação apresenta, uma abordagem acessível e portátil para realizar topografias da córnea. Os resultados obtidos com o nosso protótipo mostram uma diferença média por volta de 0.02 milimetros, equivalente a 0.5% do raio médio da córnea, quando comparadas com topografias adquiridas com um topografo comercial. Nossa abordagem é baseada no disco de Plácido, a um conjunto de círculos concêntricos que são colocados na frente do olho do paciente e refletidos na córnea. Observando a deformação do padrão projetado, podemos identificar algumas condições refrativas (e.g. astigmatismo, ceratocone) e estimar a topografia da córnea do paciente. Nós construimos um dispositivo para ser utilizado com um celular para emitir os padrões, estes são então capturados pela câmera do celular. Nós usamos um sequência de procedimentos para melhor as imagens, segmentar os padrões, associar o padrão capturado com o emitido para amostrar o sinal, e finalmente estimar a superfície da córnea. A forma estimada é então decomposta, usando-se os polinômios de Zernike, em componentes com significado ótico específico. Nós avaliamos os resultados obtidos com o nosso protótipo de três maneiras: inspeção visual de ceratoscopias, detecção de ceratocone, e comparação com os resultados produzidos por um topográfo de córnea comercial. De acordo com essa análise, nosso dispositivo pode ser utilizado para o exame de indivíduos com ceratocone, e obter topografias com 0.02 milimetros de diferença em relação aos resultados obtidos com um topógrafo comercial. / Corneal topography consists of measuring the corneal shape, which is a key factor for visual acuity. The exam is used, for instance, in keratoconus detection, personalized contact lens fitting, in pre- and post-procedures associated with refractive surgery and corneal transplants. This thesis presents an accessible, inexpensive and portable approach to perform corneal topographies. The results obtained with our prototype show a mean difference of about 0.02 millimeters, equivalent to 0.5% of the mean corneal radius, when compared to topographies acquired with a commercial device. Our approach is based on Placido’s disks, a set of concentric disks that are placed in front of the patient’s eye and reflected on the cornea. Observing the deformation of the projected pattern, one can identify some refractive conditions (e.g., astigmatism, keratoconus) and estimate the patient’s corneal topography. We have built a clip-on device to be used with a cell phone to emit the patterns, which are then captured by the cell phone camera. We use a software pipeline to enhance the images, segment the patterns, associate the emitted pattern with the captured one to sample the signal, and finally estimate the corneal surface. The estimated shape is then decomposed using Zernike polynomials in components with specific optical meanings. We have evaluated the results obtained with our prototype in three ways: visual inspection of keratoscopies, keratoconus detection, and comparison with the results produced by a commercial corneal topographer. According to such analysis, our device can be used for screening of individuals with keratoconus, and to obtain corneal topographies with 0.02-millimeter differences with respect to the results obtained with a commercial corneal topographer.

Detecção automática de regiões planares em nuvens de pontos é um importante passo para muitas aplicações gráficas, de processamento de imagens e de visão computacional. Enquanto a disponibilidade de digitalizadores a laser e a fotografia digital tem nos permitido capturar nuvens de pontos cada vez maiores, técnicas anteriores para detecção de planos são computacionalmente caras, sendo incapazes de alcançar desempenho em tempo real para conjunto de dados contendo dezenas de milhares de pontos, mesmo quando a detecção é feita de um modo não determinístico. Apresentamos uma abordagem determinística para detecção de planos em nuvens de pontos não estruturadas que apresenta complexidade computacional O(n log n) no número de amostras de entrada. Ela é baseada em um método eficiente de votação para a transformada de Hough. Nossa estratégia agrupa conjuntos de pontos aproximadamente coplanares e deposita votos para estes conjuntos em um acumulador esférico, utilizando núcleos Gaussianos trivariados. Uma comparação com as técnicas concorrentes mostra que nossa abordagem é consideravelmente mais rápida e escala significativamente melhor que as técnicas anteriores, sendo a primeira solução prática para detecção determinística de planos em nuvens de pontos grandes e não estruturadas. / Automatic detection of planar regions in point clouds is an important step for many graphics, image processing, and computer vision applications. While laser scanners and digital photography have allowed us to capture increasingly larger datasets, previous techniques are computationally expensive, being unable to achieve real-time performance for datasets containing tens of thousands of points, even when detection is performed in a non-deterministic way. We present a deterministic technique for plane detection in unorganized point clouds whose cost is O(n log n) in the number of input samples. It is based on an efficient Hough-transform voting scheme and works by clustering approximately co-planar points and by casting votes for these clusters on a spherical accumulator using a trivariate Gaussian kernel. A comparison with competing techniques shows that our approach is considerably faster and scales significantly better than previous ones, being the first practical solution for deterministic plane detection in large unorganized point clouds.