Reconhecimento de Objetos 3D Utilizando Atributosde Superfícies de Modelos Poliedrais

Maria de Fátima Santos Far-ias.'João Marques de Carvalho'

1Universidade Federal do Mar anhão - CT - DEESão Luís, MA, Brasilfarias@dee.ufpb .br

2Universidade Federal da Paraíba - CCT - DEECaixa Postal 10.105, 58109-970 Campina Grande, PB, Brasil

carvalho@dee.ufpb .br

Abstract. This paper proposes a 3D object recognition system based on the matching ofgeometric attributes extracted from polyhedral models.Resumo. Este trabalho propõe um sistema de reconhecimento de objetos 3D baseado nocasamento de atributos geométricos extraídos de modelos poliedrais.

/

1 Introdução

Este trabalho apresenta um método de reconhe-cimento de objetos em cenas tri-dimensionais ba-seado em modelos poliedrais . O reconhecimento éobtido através do casamento de atributos de super-fícies , extraídos de imagens bi-dimensionais dos ob-jetos [1] . O método consiste de três etapas: 1) cons-trução de modelos, 2) extração de características doobjeto na cena e 3) casamento de características(identificação e localização).

A figura 1 mostra o diagrama em blocos dosistema de reconhecimento proposto. A bibliotecade modelos consiste de modelos tri-dimensionais(3D) e um conjunto de atributos geométricos desuperfícies correspondente a cada um dos modelos .Na etapa de extração de características são cap-tadas três imagens do objeto as quais passam porprocessos de digitalização com extração de algu-inas características bi-dimensionais (2D). Tais ca-racterísticas são reunidas e um conjunto de atribu-tos geométricos 3D correspondentes às superfíciesvisíveis do objeto é elaborado.

Com as informações provenientes do conjuntode atributos da cena, o bloco da identificação fazuma busca na biblioteca de modelos, determinandoqual o modelo que contém aqueles atributos, atravésdo casamento de características. Nesta etapa, o sis-tema define não apenas o modelo mas também assuperfícies do mesmo correspondentes às superfíciesvisíveis na: cena. Com as informações do modeloidentificado e da cena, o sistema determina a loca-lização espacial do modelo no ambiente da cena eproduz o relatório de saída.

O casamento de características, reconhecimentopropriamente dito, ocorre em duas fases: a geração

1-- - --------------------- -----I C:.lructcrL,UclI;'I' dll ()hJctu na ccnll,, r-"--'-''---,,,

,------

Rccunhcctmentu

Figura 1: Diagrama em blocos

de hipóteses e a uerificaçiio de hípóteses. As hi-póteses são geradas a partir de atributos locais eglobais das superfícies e são verificadas (confirma-das ou não) a partir dos atributos relacionais entreas superfícies.

2 Biblioteca de Modelos

Os modelos foram elaborados no ambiente 3D dosistema CAD - AutoCAD R12, como se estivessemem repouso sobre uma mesa. Foram construídosdez modelos poliedrais representando formas pos-

52

Os atributos do modelo Mk , onde Mk EM, são:

• superfície S: área (AkS), perímetro (PkS), nor-mal (NkS), centróide (Ck..S) , número de ares-tas (NLkS) e o conjunto de vérticesJVks),

• sólido k: quantidade de superjicies (faces) (NFk),área mínima (AMI Nk J.e ârec máxima (AMAXi)das faces, número mínimo de arestas (NLMI Nç}e número máximo de (NLMAXk) dasfaces .

• superfície s: área (a.) , perímetro (p.) normal(Ti.), centróide (c.), número de arestas (nl.)e o conjunto de todos . os vértices (VC.).

AM1Nk AMAXk (1)NLMINk NLMAXk (2)

4 Casamento de características4.1 IdentificaçãoA geração de hipóteses é inicializada após a cons-tatação do seguinte lema:

Lema 4.1 O modelo k é analisado se a área e onúmero de arestas da i-ésima superfície da cenaestiverem contidos nas faixas de variações da áreae do número de arestas do modelo, ou seja:

Definição 3.2 Os atributos da cena com nf facesvisíveis são:

da segmentação. A segmentação fornece listas dosvértices em 2D que definem o contorno das su-perfícies de cada imagem. A partir destes vértices2D, são elaboradas listas contendo os vértices 3D decada superfície, através de técnica de cruzamentodos dados provenientes das imagens. '

Para os testes realizados foram sintetizadas vá-rias cenas com auxílio do AutoCAD, que forneceuas imagens de linhas correspondentes às vistas su-perior, frontal e lateral do objeto ou objetos nacena. Um programa em AutoLISP aplicado às ce-nas forneceu a lista dos vérticesSf) das superfíciesvisíveis em mais de uma vista. A partir dos vértices3D, calculou-se os demais atributos de sup.erfíciesda cena, necessários ao casamento: área, perímetro,quantidade de vértices (ou arestas) , comprimentodas arestas; centróide e normal unitária. As cenasforam elaboradas com os objetos em posições dife-rentes das utilizadas para a construção dos modeloscorrespondentes. Nas figuras de 4 a 6 são mostra-das as cenas usadas nos testes aqui relatados.

As características (atributos) dos modelos e, das cenas são formuladas da seguinte maneira:

Definição 3.1 Seja o conjunto de modelos

{,( \ ,'. I \Hollw>lo 7 : \ ' .

I

HolJ.IO 3

MCll..lelos 3D

r' 11-1;/111< f CoI f "'" ,

"'.)dele.. 2

]'- ' . -Hod.to E:t

!----,l i" ')

. " .I •. " ,

Hodelo I

1A numeração em cada modelo se refere ao número dasuperfície.

Figura 2: Vista 3D dos modelos

3 Extração de característicasA cena é composta de um ou mais objetos de su-perfícies planas que repousam sobre uma mesa. Asimagens do objeto são obtidas através de estruturaem estereoscopia passiva em que três câmeras cap-tam três imagens 2D do objeto. Estas câmeras de-vem ser colocadas na cena de modo a obter as vistassuperior, lateral e frontal do objeto, tendo a mesacomo referência.

Para cada vista foi definido uJIl plano . Para avista superior, paralela ao plano da mesa, foi defi-nido o plano XY, para a lateral o plano XZ e para afrontal o plano YZ. É importante mencionar que ascâmeras devem estar à mesma distância do centroda mesa e possuir mesmo comprimento focal paragarantir um alinhamento entre as imagens.

Cada imagem passa pelas etapas comuns depré-processamento e segmentação. A função dopré-processamento é reduzir cada uma das vistasdo objeto a uma imagem de linhas, onde apenas oscontornos das superfícies são visíveis. Estes contor-nos devem ser contínuos e bem definidos, de modo agarantir uma boa extração das superfícies na etapa

sivelmente em ambientes industriais.A figura 2 mostra a vista 3D dos modelos! quecompõem a biblioteca. Procurou-se construir gru-pos de modelos com certa semelhança de formas ede atributos geométricos entre si, como é o casodos modelos de número 1, 6, 8 e 10 bem comoos modelos 2, 3 e 4, de modo a dificultar a tarefado sistema de reconhecimento. Um programa emlinguagem AutoLISP foi elaborado e determinou oconjunto de atributos geométricos correspondente acada modelo. Os atributos de superfícies utilizadossão: vértices, quantidade de vértices, área, períme-tro, comprimento das arestas, centróide e normal.

53

Vi = {(kq;hqSl,hqs" ..·)},q= 1,2,... (7)

A geração de hipóteses encontra as superfíciescasadas isoladamente, ou seja, realiza o casamentode atributos locais e globais das superfícies inde-pendentemente uma das outras. A fase seguinte,

3. o número de arestas da i-ésima superfície dacena (nli) com o número de arestas da !-ésimasuperfície do modelo k-(NLkI) , através do se-guinte critério de erro e"';'J

1. a área da i-ésima superfície da cena (ai) com aárea da !-ésima superfície do modelo k (AkI) ,com 1 :S i :S nf e 1 :S ! :S N Fk, através doseguinte critério de erro ea :

eB= [cos é, -COSBII:S 0.28 (8)

Lema 4.2 Sejam Bi e B1 o ângulo entre as normaisde um par de superfícies da cena (ni, ni+l) e umpar do modelo (NkI, NkIH), respectivamente. SejaeB o erro angular dado pela diferença absoluta entreos cossenos destes ângulos (produtos escalares). Ocritério de erro será dado por:

onde:

cos Bi = ni .ni+lcos B1 = NkI . NkIH

Lema 4.3 Sejam dist, e dist, as distâncias entreos cenirôides' de duas superfícies da cena (Ci' Ci+l)e duas do modelo (CkI, CkI+l), respectivamente.Seja ed o erro da distância dado pela diferença ab-soluta entre as distâncias dos centróides relativa adist] , O critério de erro será dado por:

ed = Idisti - distI I < 0.10 (9)dist, - ,

20 centróide é dado pela média aritmética dos vértices,onde c. == (x .,y.,zs) e Cks = (Xks,Yk"Zks)'

a verificação de hipóteses caracteriza-se por rea-lizar casamento com atributos relacionais das su-perfícies, visando selecioná-las de acordo com suaposição espacial no sólido. A verificação procuraagrupar as superfícies hipotetizadas, tal que as rela-ções entre elas sejam as mesmas relações encontra-das entre as superfícies da cena.

Os atributos geométricos mais indicados paradeterminar as relações entre as superfícies de sólidossão a normal [2, 3, 4] e o centróide [5]. Estes valo-res são definidos em relação ao sistema de coorde-nadas onde encontra-se o objeto . Como os sistemasde coordenadas da cena e do modelo são diferentes,utilizam-se como atributos relacionais o ângulo en-tre as normais e a distância entre os centróides deduas superfícies do objeto. Na realidade, o ânguloentre as duas normais representa o ângulo entre asduas superfícies correspondentes e a distância entredois centróides representa a distância média entreas duas superfícies correspondentes.

A verificação das hipóteses ocorre em duas fa-ses. Na primeira fase as superfícies de cada mo-delo hipotetizado são agrupadas em pares tal queo ângulo entre as normais e a distância entre oscentróides das componentes de cada par casem como ângulo entre as normais e a distância entre oscentróides das componentes de um par de superfíciesna cena. Considerando que a cena pode conter umou mais objetos, são feitas todas as 'combinaçõespossíveis de pares de superfícies para esta análise,com exceção da combinação que envolve a superfíciecom ela própria. Os pares de superfícies do modelosão selecionados de acordo com os critérios de erroestabelecidos nos lemas 4.2 e 4.3 .

(6)

(3)

(5)

(4)- Ipi - PkIl < O20'ep - P _ .,kI

_ lai -AkII < O20'ea - A _.,kI

l - Inli - NLkII 020'en - N L :S .,kI

el = Icom pci - COMPMkII < 0.20.COMPMkI -

4. o comprimento de uma aresta da z-esima su-perfície da cena (compci) com o comprimentode alguma aresta da !-ésima superfície do mo-delo k (COMPMkI), através do critério deerro el:

2. perímetro da i-ésima superfície da cena (pdcom o perímetro da !-ésima superfície do mo-delo k (PkI), através do seguinte critério deerro ep :

Estas quatro restrições somadas às iniciais (eqs1-é2) geram todas as hipóteses da identificação. Oespaço de pesquisa, comparado ao espaço total, ébem reduzido e bastante confiável. O limiar fixo de0.20 nos critérios de erros é definido empiricamentee corresponde a um erro (ou diferença) máximo en-tre os atributos da cena e modelo de vinte por cento(20%) do -atributo do modelo . Ao final desta fa;se,para cada superfície i da cena é selecionado umconjunto contendo os modelos kq e as respectivassuperfícies h q casadas, ou seja:

Este lema é importante porque evita a pes-quisa à modelos com atributos fora destas faixas devalores, 'ou seja, reduz o tempo de pesquisa. Casoseja satisfeito, cada superfície do modelo k é anali-sada. Assim, a !-ésima superfície do modelo k é se-lecionada se houver simultaneamente o casamentoentre:

54

onde:I

disi, = J(Xi - xi+d2+ (Yi - Yi+1)2 + (Zi - zi+d2

disi, = J(XI - XI+1)2 + (YI - YI+d 2+ (ZI - ZI+1)2

o valor de limiar 0.28, definido empiricamente,na equação 8 corresponde a uma variação angularaproximada de 15°, próximo de O valor de li-miar 0.10 na equação 9, também definido empirica-mente, é menor que o limiar da geração de hipótesespara permitir um maior refinamento nesta seleção.

Nesta fase, procura-se uma sequência de su-perfícies na cena e nos modelos que obedeçam umdado critério de continuidade na formação dos pa-res . Por exemplo, se o par de superfícies da cena(a, b) tem como resposta o par de superfícies (v,w)em algum modelo, o próximo par de superfícies nacena a ser analisado deve ser algum que comece comb. Por sua vez, procura-se no mesmo modelo paresque começam com w, e assim por diante. Esta re-gra consegue agrupar um conjunto de superfícies nomodelo que possui a mesma sequência de ângulosque um dado grupo de superfícies na cena. Alémdisto, pode-se concluir no final desta análise qual ouquais os modelos que apresentam correspondênciacom um grupo de superfícies na cena.

Na segunda fase, a verificação final, os gruposde superfícies por modelo são analisados através deuma árvore de pesquisa contendo todos os paresselecionados. A melhor combinação de pares cor-responde a um caminho em que não há repetição defaces e o segundo elemento do último par coincidecom o primeiro elemento do par que iniciou a pes-quisa. As superfícies que compõem este caminho daárvore de pesquisa são as superfícies procuradas.

Elabora-se assim uma lista dos resultados en-contrados contendo os modelos ordenados na or-dem decrescente da quantidade de superfícies iden-tificadas. Esta ordem indica os modelos mais pro-váveis e são eliminados os que têm superfícies cor-respondentes à superfícies da cena já identificadaspor outro modelo de prioridade maior.

4.2 Localização

Determinar a localização do modelo identificado nacena é o mesmo que reconstruir o modelo no sis-tema de referência da cena. Este processo de re-construção ocorre através de transformaçõês geo-métricas que! transportam o modelo elaborado nosistema de referência do AutoCAD para dentro doIsistema de coordenadas da cena, o mundo real. Taistransformaçõks envolvem operações de translaçõese rotações de superfícies no espaço 3D de acordocom os passos ilustrados na Figura 3:

1. Traçar a superfície do modelo no sistema decoordenadas da cena.

2. Transladar as superfícies da cena e modelo paraorigem tal que a origem coincida com os cen-tróides de cada superfície.

3. Rotacionar a superfície do modelo tal que suanormal coincida com a normal da superfície dacena.

4. Rotacionar a superfície do modelo tal que umade suas arestas coincida com uma aresta dasuperfície da cena.

5. Transladar as superfícies da cena e modelo atéa posição original da superfície da cena.

Os passos acima traduzem a necessidade deapenas duas .matrizes de Transformações: MT1 eMT2 • MT1 é composta da translação do item 2 eda rotação do item 3. A matriz MT2 é compostada rotação do item 4 e da translação do item 5. Oângulo e o eixo de rotação para MT1 são calcula-dos com as normais das superfícies casadas (da cenane e do modelo nm ) . O ângulo é obtido através doproduto escalar (cos B1 = fie ' iim) e o eixo pelo pro-duto vetorial (vr = iimx fie)' Para MT2 , calcula-seinicialmente o ponto médio de duas arestas casadas(da cena pme e do modelo pmm)' Uma vez que am-bas superfícies estão na origem, calcula-se o ânguloatravés dos vetores normalizados dos pontos médios(cos B2 = . 11=:11); o eixo de rotação destamatriz coincide com própria normal da superfícieda cena.

5 Resultados e ConclusõesO método de reconhecimento foi implementado emlinguagem C e testado em vinte e quatro cenas,sendo dez com objetos isolados. As Figuras 4, 5 e6 mostram cenas com objeto isolado, dois objetose três objetos, respectivamente. A tabela 1 mostraos resultados obtidos durante a fase de geração dehipôteséspara cada cena (eq. 7). As tabelas 2,3 e 4 mostram as fases da verificação de hipótesesdas cenas indicando os grupos de superfícies pormodelos correspondentes à grupos de superfícies dacena'' (eqs. 8 e 9) e os resultados. finais com a identi-ficação das superfícies . Para a cena 2, por exemplo,as superfícies 1, 2, 3 e 7 da cena foram identificadascomo sendo respectivamente as superfícies 3, 2, 4e 7 do modelo 7 e as superfícies 4, 5 e 6 da cenacomo sendo respectivamente as superfícies 3, 5 e 8do modelo 8.

Os resultados encontrados foram muito bons,todos os objetos nas cenas foram corretamente iden-tificados. A tabela 5 mostra a distância média,d, entre os vértices de cada superfície dos modeloscom os vértices das superfícies da cena correspon-dentes, conseguidos na etapa de localização. O pior

3 Indicadas com x.

55

Figura. 3: Passos para a localização

'0 -""""''''• 2

= ======'A · 1

.__l.illll.l__

Figura 4: Cena 1

caso verificou-se na cena 3, Çi= 0.37cm. Como a or-dem de grandeza dos comprimentos está em tornode 10cm, este .valor é insignificante.

resultados comprovam a eficiência do mé-todo e mostram que pode ser aplicado em sistemasde visão para automação industrial, quer seja emtarefas de identificação ou em localização de partesdó objeto. As principais características do métododesenvolvido são : eficiência na convergência parao resultado correto , simplicidade de cálculos, baixoesforço computacional, baixo custo , facil idades deconstrução e ampliação da.biblioteca de modelos.

Referências

[1] MARSHALL, A. D. AND MARTIN, R. R . Com-puter Vision, Models and Inspection . WorldScientific, 4,1992.

"'P.' '''' 0'( 11\\/

.Figura 5: Cena 2

[2] GRIMSON, W. L. AND L.-PÉREZ, T . Model- 'Recognition . and Localization frorn

Sparse Range or Tactile Data. The IJRR,3(3) :3-35, 1984. .

[3] MURRAY, D . W . Model-Based RecognitionUsing 3D Shape Alone. CVGIP, (40):250-266,1987.

[4] KLEMT, A. AND INFANTOSI, A. F. C. Classifi-cation of Surface NormaIs in a Tutorial Microc.-Based System for Anatomy. Proc. of 98th.MWSCAS - Brasil, 2:1373-1376,1995.

[5] OSHIMA, M. AND 8HIRAI, Y. Object Recog-nition Using Three-Dimensional Information.IEEE Trans. PAMI, 5(4) :353-361, May 1983.

56

.. l.b==========d[] z.,..,

x l..·..Figura. 6: Cena 3

Tabela 3' Verificação - Cena 2

Tabela 4: Verificação - Cena 3

s.l s .2 s.3 s.4 s.5 s .6 s.7 Mod .x x x x 7

x x x 83 2 4 7 7

3 5 8 8

s.l s.2 s .3 s.4 s .5 s.6 s.7 s .8 s.9 Mod .x x x x 1

x x x 3x x 6

2 3 1 4 13 4 5 3

7 5 6

..--=__Tabela 1: Geração de hipótesesCena I sup .Cena I Vsie un od ; sup casadas),1 s.l (6; 5 8)

.!(10; 6 9)

s .2 (1; 3 6)(6; 6 9)(10; 7 10)

s.3 (6; 4)s.4 (1; 3 6)

(6; 6 9)(10 ; 7 10)

2 s.l (7; 3 6)s.2 (1; 3 6)

(7; 1 2 3 4 6)(10; 7 10)

s .3 (1; 3 6)(7; 1 2346)(10 ; 7 10)

s.4 (8; 3 8)s .5 (6; 6 9)

(7; 2 3 4 6)(8; 1 2 5 6)

s .6 (8; 3 8)s.7 (7; 5 7)

3 8.1 (1; 2 5)s.2 (1; 2 5)

(6; 7)(10 ; 5 8)

8.3 (1; 3 6)(6; 6 9)(10 ; 7 10)

s.4 (1; 1 4)8.5 (3; 3 4 5 6 7 8 9 10)s .6 (3; 3 4 5 6 7 8 9 10)s.7 (3; 3 4 5 6 7 8 9 10)s.8 (6; 5 8)8.9 (1; 1 4)

57