Segmen ación y clasi icación de
mallas 3D
Mas e Uni e si a io en Au omá ica e In o má ica Indus ial
Uni e sidad Poli écnica de Valencia
ALUMNO: Bo ja Ja ie He áez Concejo
DIRECTOR: Edua do Vend ell Vidal
2
3
Índice
1.- INTRODUCCIÓN ........................................................................................................................ 4
2.- ESTADO DEL ARTE .................................................................................................................... 8
2.1 Segmen ación ...................................................................................................................... 8
2.1.1 Segmen ación de imágenes ......................................................................................... 9
2.1.2 Nubes de pun os ........................................................................................................ 15
2.1.3 Mallas 3D .................................................................................................................... 18
2.2. Resumen ........................................................................................................................... 25
2.3 Jus i icación del mé odo elegido ....................................................................................... 28
3.- SOLUCIÓN PROPUESTA .......................................................................................................... 29
3.1 Dis inción de ca as planas ................................................................................................. 30
3.1.1 Iden i icación de los iángulos/ ace as semilla ......................................................... 31
3.1.2 Expansión de la egión. .............................................................................................. 31
3.1.3 Colo eado de las egiones. ......................................................................................... 35
3.2 Dis inción de ca ac e ís icas .............................................................................................. 37
4.- EJEMPLO DE APLICACIÓN ....................................................................................................... 47
5.-RESULTADOS ........................................................................................................................... 52
5.1 Plan eamien o ................................................................................................................... 52
5.2 Análisis y conside aciones ................................................................................................. 55
5.3 Compa ación edi icio modelado s. edi icio escaneado ................................................... 59
5.4 Compa ación de iempos de búsqueda de pa ones ........................................................ 60
6.- CONCLUSIONES Y POSIBLES AMPLIACIONES ......................................................................... 63
6.1 Conclusiones...................................................................................................................... 63
6.2 Ampliaciones u u as ......................................................................................................... 64
7.- REFERENCIAS .......................................................................................................................... 65
4
1.- INTRODUCCIÓN
El p esen e abajo inal de mas e p e ende abo da el p oblema de la segmen ación de
mallas poligonales en ocada a modelos que ep esen en edi icios eales, es deci , se capaces
de econoce ca ac e ís icas sob e modelos geomé icos en endiendo po ca ac e ís icas esas
po ciones del modelo que di ie en de la es uc u a p incipal, ales como salien es,
dep esiones, aguje os, e c. En el caso que nos ocupa, en ocado conc e amen e a edi icios, el
obje i o es di e encia y econoce los elemen os que no son pa ed o achada como pue as,
en anas, e c.
Según el dicciona io de la lengua española la “segmen ación” se de ine como el ac o de di idi
o o ma pa es o segmen os, siendo un segmen o una po ción o pa e co ada o sepa ada de
una cosa, de un elemen o geomé ico o de un “ odo”. Es e mé odo se aplica en muchos
ámbi os de la ida dia ia, po ejemplo en economía se u iliza el é mino “segmen ación de
me cados” donde se segmen a una masa g ande de consumido es en un g upo educido que
son los clien es po enciales [1]. En biología se u iliza el é mino pa a deno a la di isión de
algunos animales y plan as en una se ie de segmen os epe i i os [2]. En el ámbi o de la
in o má ica, que es el que nos ocupa y más conc e amen e en la de ección de elemen os y
ca ac e ís icas de un edi icio, que es el obje i o plan eado en es a esina, se ha aplicado la
segmen ación a pa i de di e en es supues os según el o ma o del modelo disponible:
imágenes, nubes de pun os y modelos idimensionales poligonales (mallas 3D).
En el caso de dispone de imágenes, la segmen ación se e ie e a la pa ición de una imagen
en un conjun o de egiones que la cub en. El obje i o en muchas a eas es que las egiones
ep esen en á eas signi ica i as de la imagen, como po ejemplo, los cul i os, zonas u banas o
bosques en una imagen de un sa éli e. Cuando las egiones de in e és no cub en oda la
imagen, se puede segui hablando de segmen ación, pe o en es e caso hablamos de
segmen ación de las egiones de in e és y egiones del ondo de la imagen a igno a . La
segmen ación de imágenes iene dos obje i os, el p ime o descompone la imagen en pa es
pa a su pos e io análisis y el segundo hace un cambio de ep esen ación. Los pixeles de la
imagen deben es a o ganizados en unidades de más al o ni el, es deci que es as
ag upaciones engan mayo signi icado o sean más e icien es pa a su análisis [3].
5
Ilus ación 1: Ejemplo de segmen ación de imágenes (Fuen e: Jamie Sho on e .al. 2006).
Cuando se ealiza un p oceso de escaneado 3D de un obje o eal, el esul ado más habi ual es
el de una nube de pun os de la supe icie del obje o escaneado. Se a a de un mé odo
comúnmen e u ilizado en a qui ec u a a la ho a de ealiza le an amien os de edi icios
exis en es pa a su es udio [4]. La segmen ación de una nube de pun os consis e en o ganiza ,
pa ame iza y pos -p ocesa los pun os 3D que con iene pa a ag upa los en elemen os
iden i icables. Es a o ganización depende de las cie as ca ac e ís icas homogéneas que
p esen an los pun os de la nube, un c i e io de homogeneidad se ia la cu a u a o las ca as
planas de inidas po un conjun o de pun os [5].
Usualmen e las nubes de pun os eciben un a amien o pos e io de econs ucción de ca a a
ob ene un modelo geomé ico poligonal o malla 3D iangula del obje o escaneado. Se a a
del mé odo más usual a la ho a de ep esen a un obje o en un compu ado .
Ilus ación 2: Segmen ación de nubes de pun os (Fuen e: Hui Lin, Jizhou Gao e al. 2013).
Segmen a una malla 3D consis e en la sepa ación de la misma en pa es di e en es, aunque
no signi ica necesa iamen e sepa a la malla en sí, si no que ambién se u ilizan los
p ocedimien os necesa ios pa a llega a esa clasi icación de pa es que es lo que indica a a qué
g upos (elemen os o ca ac e ís icas) pe enece cada iangulo. Pos e io men e se asigna á a

6
cada g upo una e ique a, dependiendo de ca ac e ís icas geomé icas. Es habi ual iden i ica
los iángulos pe enecien es a una ca ac e ís ica o elemen o de e minado median e un colo ,
que acaba á iden i icando la misma pa e semán ica del obje o.
Ilus ación 3: Segmen ación de mallas 3D (Fuen e: E. Kaloge akis e al. 2010).
Es e abajo in de mas e su gió con la idea de con inua y se una ex ensión de un p oyec o
colabo a i o en e el G upo de Robó ica del Ins i u o Uni e si a io de Au omá ica e
In o má ica Indus ial (AI2) de la Uni e si a Poli ècnica de València y el Dipa amen o di
A chi e u a de la Uni e si à degli S udi di Fi enze [6]. En conc e o, es a colabo ación se
plasma en el apoyo ecnológico po pa e del AI2 a los p ocesos de le an amien o que lle an a
cabo en Dipa amen o di A chi e u a de la Uni e si à degli S udi di Fi enze.
Un le an amien o a qui ec ónico consis e en el conocimien o comple o de lo ela i o a la
es uc u a de un edi icio po lo que en es e sen ido los sis emas in o má icos pueden ayuda
en el almacenamien o y ges ión de la in o mación como pueden se da os, dibujos, planos, e c.
El abajo de colabo ación se ha plasmado sob e el es udio ealizado en el pueblo de
Pie abuona en la egión de la Toscana, I alia.
Pa a es e p opósi o, se ealizó una aplicación que elaciona un sis ema de in o mación con los
modelos 3D de es a ciudad. A pa i de los modelos de los edi icios ob enidos con escáne es
lase , la nube de pun os esul an es se a a on con un so wa e de poligonización que los
ans o mó los pun os en una malla iangula . Po o o lado el sis ema de in o mación
u ilizado en p ime a ins ancia es un GIS (Geog aphic In o ma ion Sys em) diseñado pa a
cap u a , almacena , analiza , maneja y p esen a odo ipo de da os geog á icos [7]. A pa i
de es e esquema se diseñó una aplicación que pe mi ía po un lado in oduci in o mación a
los modelos (“Back-end”, mos ado en la ilus ación 4) selecciona las pa es de la malla 3D y la
pos e io in oducción de in o mación ela i a a és as, lo que con o ma un p oceso de
e ique ado semán ico manual, es deci , asigna un conjun o de in o mación a un g upo de
iángulos que o man una pa e de la es uc u a del edi icio. El p oblema adica en que es e
p oceso es cos oso empo almen e hablando pa a el usua io y equie e de mucha epe ición.
7
Po o a pa e exis e un “F on -end”, en el que se pe mi e la isualización de la in o mación
in oducida en el sis ema. Pa a la cla i icación del sis ema o al se mues a la siguien e imagen.
Ilus ación 4: Esquema gene al uncionamien o (Fuen e:”Ap oximación a la ges ión de modelos 3D pa a el
le an amien o a qui ec ónico”.And és Ga cía. 2014).
La ac ual esina de mas e p e ende se una ap oximación a un e ique ado semán ico
au omá ico, que sea capaz de econoce las pa es del obje o idimensional y así se les pueda
asigna in o mación según su ipo, pe mi iendo que en un u u o pueda añadi se al desa ollo
an e io y eduzca los iempos que equie e el usua io pa a ealiza es e p oceso de mane a
manual.
Pa a ello se ha ealizado un algo i mo que es capaz de iden i ica y e ique a a un conjun o de
iángulos los cuales o man pa e de un elemen o de la achada del edi icio u obje o 3D. En
es e caso se en iende po “e ique a” al nomb e que desc ibe ese elemen o, po ejemplo
“pue a”, “ en ana” o “pa ed” y que es á ep esen ado po un colo conc e o.
8
2.- ESTADO DEL ARTE
El p incipal p oblema de es e abajo in de mas e es el de abo da el p oblema de
econocimien o de ca ac e ís icas de e minadas en una malla 3D. La palab a “ca ac e ís ica”
( ea u e en inglés) iene di e en es signi icados según el con ex o dependiendo del dominio
especí ico. Po ejemplo, en diseño puede e e i se a una muesca, mien as que en
manu ac u ación se e ie e a huecos o aguje os, po o o lado en inspección la palab a
“ca ac e ís ica” se usa como da o o e e encia de una pa e. La clasi icación de ca ac e ís icas
es o almen e dependien e de la aplicación. Es muy di ícil hace una clasi icación de
ca ac e ís icas independien e de la aplicación [8]. Algunas de las de iniciones que se pueden
encon a en la bibliog a ía son las siguien es:
 “Una ca ac e ís ica es una en idad usada en el azonamien o del diseño, ingenie ía o
manu ac u ación de un p oduc o” [9].
 “Una o ma geomé ica o en idad cuya p esencia o dimensiones son eque idas pa a
ealiza al menos una unción CIM y cuya disponibilidad como p imi i a pe mi e que
ocu a el p oceso de diseño” [10].
 Una ca ac e ís ica ambién puede se de inida gene almen e como un conjun o de
en idades geomé icas que ienen pa ones opológicos y geomé icos únicos a esa
ca ac e ís ica [11].
Emad S. Abouel Nas y Ali K. Kam ani [12] es ipulan que la base de es as de iniciones es que las
ca ac e ís icas ep esen an el signi icado de ingenie ía de la geome ía de la pa e,
ensamblado u o a ac i idad de manu ac u a. Con ello, apo an una de inición p opia en la que
una ca ac e ís ica es una cons i uyen e ísica de una pa e diseñada mapeable a una o ma
gené ica y que iene ele ancia en la ingenie ía.
El p oblema que se plan ea en es e abajo in de mas e consis e en onces en de ec a es as
ca ac e ís icas sob e las mallas idimensionales, u ilizándose pa a ello un mé odo de
segmen ación que se explica á en el capí ulo 3 de es e documen o.
2.1 Segmen ación
Como ya se ha dicho an e io men e la segmen ación se de ine como el ac o de di idi o o ma
pa es o segmen os. En el caso que nos ocupa el obje i o es sepa a la malla 3D en pa es
signi ica i as pa a en ende y econoce o mas o ca ac e ís icas de la misma.
En [13] se indica que la segmen ación de mallas, y de o ma más gene al la segmen ación de
o mas, se puede in e p e a de mane a pu amen e geomé ica o de mane a más o ien ada a
la semán ica. La p ime a sepa a la malla en un núme o de conjun os que son uni o mes
espec o a una p opiedad, en la segunda el obje i o es iden i ica pa es que co esponden con
ca ac e ís icas ele an es de la o ma o olumen del obje o.
9
Las mallas 3D y la segmen ación de és as se desc ibe de mane a o mal en [14] de la siguien e
mane a:
 Una malla idimensional M es á de inida po una upla {V, E, F}, donde los é ices
son V = {pi| pi ϵ Ʀ3, 1≤i≤m}, las a is as son E = {eij = (pi, pj)| pi, pj ϵ V, i ≠ j } y F son
las ca as, usualmen e iángulos F = { ijk = (pi, pj, pk) | pi, pj, pk ϵ V, i ≠ j, i ≠ k, j ≠ k }.
También de ine la segmen ación de una malla como:
 Sea M una malla 3D y S el conjun o de elemen os de la malla que pueden se V, E o F.
Una segmen ación Σ de M es el conjun o de sub-mallas Σ = {M0, …, Mk-1} inducidas
po una pa ición de S en k sub-conjun os disjun os.
Así pues, la segmen ación de una malla depende del c i e io que se siga pa a de e mina que
elemen os de és a (el conjun o “S” de é ices o a is as, e c.) o man pa e del mismo
conjun o. En la li e a u a exis en di e en es ipos de algo i mos pa a consegui es e p opósi o
y es e mé odo se aplica a o os ámbi os elacionados con el que nos ocupa como la
segmen ación de imágenes o la segmen ación de nubes de pun os.
2.1.1 Segmen ación de imágenes
Es un mecanismo usado pa a di idi la imagen en múl iples segmen os. El p oceso ambién
ayuda a encon a egiones de in e és en una imagen especí ica. El obje i o p ima io es el de
hace la imagen más simple y con más signi icado. Cada segmen o simboliza a un ipo de
in o mación, ya sea colo , in ensidad o ex u a. Gene almen e el p oceso de segmen ación
asigna a un alo a cada pixel de la imagen pa a que sea ácil di e encia cada egión
encon ada.
La segmen ación de imágenes sigue siendo hoy en día un p oblema desa ian e y uno de los
pasos cla e pa a el en endimien o de las imágenes. Una g an a iedad de aplicaciones como
econocimien o de obje os, codi icación o ano ación de imágenes usan el algún momen o un
algo i mo de segmen ación, y campos como el médico o mili a lo u ilizan dia iamen e. Exis en
a ias écnicas pa a segmen a imágenes, algunas de las cuales se explica an a con inuación.
2.1.1.1 Segmen ación de Imágenes po umb alización
Es as écnicas se basan en la umb alización de his og amas pa a segmen a las imágenes.
Umb aliza signi ica es ablece lími es/umb ales según los cuales se ealiza una opción u o a.
Los his og amas se de inen como una g á ica que indica el núme o de ocu encias de unos
alo es de e minados. En el caso de imágenes, se e ie e usualmen e al núme o de apa iciones
de los alo es de colo que pueden ene los píxeles.
16
de “ρ” pa a los pun os de la nube. Después el iple e {θ, ϕ, ρ}, cada uno ep esen a un único
plano que se analiza pa a un ecuen o ecu en e, los planos que llegan a cie o con eo se
ienen en conside ación como posibles planos. No obs an e es e p oceso esul a en nume osos
planos alsos, po lo que muchas implemen aciones u ilizan es icciones adicionales pa a
aumen a su e iciencia, po ejemplo un mé odo consis e en combina la ans o mada de
Hough con planos de suelo pa a elimina alsos posi i os en el algo i mo, después se e ina
oda ía más aplicando la ans o mada de Hough en 2D pa a elimina planos adicionales [43].
El es udio de las á eas que gene an las p oyecciones de clus e s de pun os se añade como una
es icción pos e io a es a écnica en [44].
Ilus ación 10: Recons ucción conseguida po [43] u ilizando la ans o mada de Hough.
Po o a pa e, el algo i mo de RANSAC (RANdom SAmple Consensus) [45], mues ea de o ma
alea o ia e i e a i a el meno núme o de pun os necesa ios pa a de e mina los pa áme os
del modelo. En onces, es os pa áme os se es ean con el es o de pun os. El p oceso se
de iene cuando un núme o de e minado de pun os del es o de da os encajan con los
pa áme os hallados. En es e pun o, los pa áme os se ees iman con el nue o conjun o de
pun os. El mé odo de RANSAC se aplica al conjun o en e o de pun os y gene a en su
e minación un solo conjun o de pa áme os. Es e algo i mo ambién ha sido u ilizado con el
obje i o de es ima planos sob e nubes de pun os de edi icios pa a su pos e io econs ucción
idimensional, pe o de la misma mane a que la ans o mada de Hough, puede gene a alsos
posi i os, sob e odo si no se aplican es icciones adicionales o el conjun o de da os con iene
uido. Un ejemplo de uso básico del algo i mo de RANSAC se iene en [46].
El p oblema de las nubes de pun os es que gene almen e su en despe ec os debido a
impe ecciones en el escaneado como uido, aguje os, e c. Es e p oblema es sol en ado
calculando p opiedades locales pa a cada pun o, como el alo de mues eo o la des iación
es ánda . Después el p incipio de RANSAC es u ilizado pa a de ec a p imi i as en la nube de
pun os, ac o seguido se ex aen pun os de los bo des de cada p imi i a y se op imizan es os
bo des. Finalmen e se c ea una malla con cada bo de de ec ado y se ensamblan pa a o ma la
malla inal [47].
En el segundo a ículo, se hace un análisis de los alo es p opios de cada pun o de la nube pa a
de e mina su plana idad, los obje os no planos son desca ados del p oceso pa a ga an iza
más obus ez en el mé odo. En el siguien e paso se u iliza el algo i mo uzzy c-medias sob e el
es o de pun os pa a ag upa los en segmen os de ejados basándose en la no mal de su
supe icie.

17
Las nubes de pun os ex aídas con escáne es LIDAR (Ligh De ec ion And Ranging) son
u ilizadas pa a econs ui ejados de edi icios a base de planos, después se ex ienden es os
planos has a el suelo con el obje i o de consegui modelos simples de edi icios. Una aplicación
de es o es una mejo a de la ans o mada de Hough u ilizada pa a de ec a múl iples planos al
mismo iempo, después se u ilizan g a os de adyacencia y se consigue es ablece elaciones
en e es os planos pa a ob ene esul ados egula es [48]. O a me odología consis e en el
análisis de los alo es p opios de cada pun o de la nube pa a de e mina su plana idad, los
obje os no planos se desca an del p oceso pa a ga an iza más obus ez en el mé odo. En el
siguien e paso el algo i mo “ uzzy” c-medias es u ilizado sob e el es o de pun os pa a
ag upa los en segmen os de ejados omando como c i e io la no mal de su supe icie [49].
Un mé odo semiau omá ico de econs ucción de achadas que jun a la in o mación de los
escáne es lase y las imágenes de los edi icios es de inido en [50]. P ime o se econoce la
es uc u a gene al de la achada con los da os del escáne , luego se ex aen los bo des de las
imágenes u ilizando el mé odo “Canny” de de ección de bo des [51] y la ans o mada de
Hough, a con inuación se compa an los esul ados con el modelo ob enido del escáne pa a
mejo a los bo des ex aídos. Finalmen e se u ilizan las ex u as con mejo isibilidad del
conjun o de imágenes y se aplican sob e el modelo 3D.
Los modelos digi ales de ele ación son u ilizados pa a segmen a y clasi ica obje os de nubes
de pun os sob e un en o no u bano. P ime o se segmen a el suelo y se de ec an los obje os
como discon inuidades en el suelo. En onces se u iliza el algo i mo wa e shed pa a sepa a los
obje os. Finalmen e se clasi ican los obje os usando una máquina de ec o es de sopo e,
“suppo ec o ma chine(SVM)” con ca ac e ís icas geomé icas y con ex uales [52].
Un abajo sob e nubes de pun os en ocado a la manipulación obó ica se p esen a en [53]. Un
sis ema ecibe como en ada una nube de pun os, los obje os son segmen ados po is as
pa ciales y se econs uyen encajando p imi i as como planos, es e as o cilind os. Se calculan
coe icien es geomé icos que ayudan a econs ui las pa es pe didas del paso an e io . Po lo
que al inal se iene un sis ema hib ido, que combina los modelos geomé icos con las mallas
pa a c ea una supe icie sua e.
18
Ilus ación 11: Sis ema híb ido o ma-supe icie [53].
O a écnica exis en e descompone la nube de pun os en p imi i as como es e as o cilind os
ayudándose del algo i mo de RANSAC, seguidamen e un g a o llamado “g a o opológico” se
cons uye ep esen ando las elaciones exis en es en e las di e en es o mas. Cada
ca ac e ís ica de la malla es ep esen ada como un g a o llamado “g a o es ingido”. Así se
buscan coincidencias en e es os g a os es ingidos y los g a os opológicos, y aplicando o as
es icciones den o del algo i mo de compa ación de g a os, se consigue de ec a las
ca ac e ís icas [54]. El mé odo que p esen a es e abajo inal de mas e es á basado en pa e
en es a me odología.
2.1.3 Mallas 3D
2.1.3.1 ¿Qué es una malla 3D?
Las mallas 3D o mallas poligonales son ep esen aciones idimensionales de una supe icie,
que se basan en una colección de é ices unidos po a is as. Un é ice se de ine como un
pun o en el espacio idimensional y que puede almacena cie a in o mación, una a is a une 2
é ices y es un pun o de unión en e 2 iángulos, 3 é ices di e en es unidos po a is as
o man una ace a/ iángulos, que es la unidad básica de ep esen ación de los polígonos
idimensionales. Algunos sis emas u ilizan polígonos c eados po 4 é ices, no obs an e
in e namen e se ep esen en como 2 iángulos. Un conjun o de ca as o polígonos unidos
en e sí, o man una supe icie.
19
Aunque se puede cons ui una malla de mane a manual especi icando é ices y ca as, es
mucho más e icien e u iliza el conjun o de he amien as so wa e pa a g á icos 3d que
exis en ac ualmen e. Es os p og amas hacen uso de la subdi isión y la ex usión. La subdi isión
como su p opio nomb e indica, acciona los iángulos en o os más pequeños añadiendo
é ices y a is as. Po o o lado, la ex usión se aplica a un iángulo o a un conjun o de ellos.
Siguiendo el con o no de es as ace as se c ea una nue a con la misma o ma, que conec a
cada uno de sus é ices con una a is a c eando un olumen. Así pues la ex usión de un
cuad ado se ía un p isma.
Las mallas poligonales se pueden clasi ica según el mé odo que se u ilice pa a almacena su
in o mación.
En las ablas é ice- é ice, se indica pa a cada é ice su coo denada en el espacio y la lis a
de o os é ices con los que conec a. Es la ep esen ación más sencilla de implemen a , pe o
se iene que in e i la in o mación de las a is as y las ca as, ya que solo se iene la in o mación
de los é ices, lo que di icul a los cálculos y ope aciones [55].
Po o o lado es án las ablas ca a- é ice, que consis e en dos ablas, una abla de ca as con
los é ices que componen cada una, y una abla de é ices que indica pa a cada é ice su
coo denada espacial y el conjun o de ca as que lo incluye. Es la ep esen ación más usada.
Tiene la en aja de que cambios en la geome ía del obje o, ep esen an ac ualizaciones en la
abla de é ices, pe o no en la abla de ca as, ya que la conec i idad en las ca as con los
é ices exis en es sigue siendo la misma. Las des en ajas que p esen a es e mé odo son po
una pa e, que la in o mación de las a is as sigue siendo implíci a y po o o lado, ealiza las
ope aciones “di isión” o “unión” de mallas es más complejo con es a ep esen ación.
O a ep esen ación muy u ilizada es la ep esen ación “a is a-alada” [56]. Se basa en
p opo ciona pa a cada a is a los 2 é ices que la de inen, las ca as a las que pe enece y las 4
a is as más ce canas con las que conec a, 2 en el sen ido ho a io y 2 en el sen ido an iho a io.
Con es e mé odo se ep esen an de mane a explíci a los é ices, a is as y ca as del modelo, lo
que o ece una g an lexibilidad a la ho a de cambia la geome ía de la malla, además las
ope aciones de unión y di isión se hacen de mane a ápida.
Ilus ación 12: Rep esen ación a is a alada (winged edge).
20
2.1.3.2 Region G owing
P ime amen e se ienen los algo i mos de c ecimien o/expansión de egiones o “ egión
g owing”, que al igual que con imágenes, consis en en que los conjun os de elemen os
solución se o man expandiendo di e en es elemen os semilla (“seed” en inglés), que son
é ices, iángulos o egiones. Luego un conjun o de eglas se aplica pa a sabe si a pa i de
es a semilla se expande más el conjun o o se de iene la expansión. Es e algo i mo es aplicado
sob e imágenes en [57] y se ex endió pa a pode aplica lo sob e mallas 3D [58]. O a solución
consis e en que los pun os se e ique en según su cu a u a Gaussiana. E ique ando los é ices
con una al a cu a u a nega i a como “pun os de on e a”, y seleccionando pun os que no
son de on e a como semillas pa a comenza el c ecimien o de las egiones en [59].
2.1.3.3 Wa e sheds
O o mé odo pa a segmen a mallas consis e en u iliza el algo i mo “wa e sheds” (en español
“línea de di isión de aguas”) usado pa a imágenes 2D, es una écnica de segmen ación que
pe mi e ex ae las on e as de las egiones de la imagen. Combina la de ección de con o nos
y c ecimien o de egiones al mismo iempo. Pa a acla a la explicación, se puede conside a
una imagen con escala de g ises como la imagen opog á ica de un elie e e es e, a cada
pixel se le asocia ía como “al u a” el co espondien e ni el de g is, así los alo es de g ises
más al os se ian “mon añas”, mien as que los alo es meno es se ian “ alles”. T as es o se
aplica un p oceso de “inundación” desde los ni eles más al os a los más bajos, la inundación
con inúa has a que “ alles” con iguos se unen, o mando las líneas de unión que ep esen an
las on e as de la imagen. Al u iliza es e algo i mo pa a obje os 3D se aplica una unción de
“wa e sehed” :R3R que guía las cuencas pa a iden i ica las c es as de la malla. Hay una
co espondencia 1 a 1 en e el mínimo de la unción “ ” y las cuencas [60]. Las a is as del
obje o son u ilizadas pa a llega al mínimo a a és de la “inundación” usando el ángulo died o
en e las a is as [61].
La écnica “Fas Ma ching Wa e sheds” segmen a la malla poligonal en pa es isuales. Lo que
busca el algo i mo es que se cumpla la eo ía llamada “minima ule” que desc ibe como la
pe cepción humana descompone los obje os en sus di e en es pa es. Es a egla de ine los
lími es de las pa es sob e líneas de cu a u a nega i a mínima, y po o o lado, se busca
man ene la obus ez del algo i mo “wa e shed”. Pa a ello se aplica un algo i mo basado en la
es uc u a de da os “heap”, pa a adap a el “wa e shed” a mallas idimensionales. También
se de ine un mapa di eccional de al u a pa a la aplicación de la “minima ule” usando alo es
de cu a u a local [62].
2.1.3.4 Mé odos basados en g a os
Los p ocedimien os desc i os a con inuación u ilizan g a os pa a adqui i in o mación
opológica de la malla idimensional, y en unción de es os in ie en p opiedades. Un g a o
21
especial llamado “Gene alized Edge-Face G aph (GEFG)” es c eado en [63] pa a iden i ica y
clasi ica las ca ac e ís icas del obje o, como son salien es, dep esiones o aguje os. Es e g a o
con iene la in o mación opológica de los con o nos de la igu a según sus ca as y en base a él
se hace un análisis de la conec i idad de a is as y ca as, es o jun o con o as conside aciones
geomé icas pe mi e di e encia es as ca ac e ís icas.
En o o mé odo, salien es Y dep esiones del obje o se ep esen an como “g a os de ca idad”,
que e lejan la in e sección o ca idad exis en e en e dos ca as. Los nodos del g a o
ep esen an la o ien ación ela i a de las ca as. En siguien es pasos se ealiza un análisis de
es os g a os pa a la clasi icación de ca ac e ís icas [64].
Ilus ación 13: G a o de ca ac e ís icas de M.Ma e a y R.L.Kashyap [64].
2.1.3.5 Mé odos basados en modelos
Se o man modelos a a és de la supe icie de la malla pa a consegui segmen a la.
Dis ibuciones de ca ga eléc ica sob e la supe icie son u ilizadas en [65], la ca ga es muy baja
en á eas de mucha conca idad de la supe icie, y muy al a en á eas de con exidad. Las á eas
de segmen ación son en onces las á eas con ca ga mínima. Los con o nos son azados donde
los mínimos de ca gas locales exis en, es os con o nos son los lími es que de inen la
segmen ación.
2.1.3.6 Mé odos basados en esquele os
El esquele o de los obje os es ob enido pa a guia la segmen ación. La supe icie de los obje os
es simpli icada median e el mé odo de con acción de a is as, más a de un plano ba e las
a is as del esquele o con el in de halla las á eas de segmen ación del obje o. La in e sección
del plano y la malla esul a en uno o más con o nos de polígonos. La o ma en que es os
con o nos a ían es examinada según cambia el plano de ba ido. Se de inen unciones
pa amé icas en es os con o nos, los con o nos que con ienen pun os c í icos en es as
unciones, o ma án pa e de los con o nos lími e de la segmen ación [66].

22
Ilus ación 14: Ejemplo segmen ación basada en esquele os [66].
2.1.3.7 Mé odos basados en clus e s
Los mé odos de clus e s (en español acimo o g upo) y de c ecimien o de egiones son
simila es. En los clus e s los ep esen an es an cambiando en base a una unción de
minimización, mien as que en los mé odos de c ecimien o de egiones, los elemen os semilla
se eligen al p incipio del algo i mo y no cambian.
Un algo i mo exis en e descompone la malla en pa ches. Se oma la decisión de si dos ca as
de e minadas deben pe enece al mismo pa che. El c i e io u ilizado es la “p oximidad” de las
ca as, en es e caso la p oximidad ísica, que se calcula como la suma de las dis ancias en e los
cen os de masa de las ca as, y a ello se le suma la dis ancia angula , calculada como el ángulo
died o [67].
El algo i mo de “K-means” es u ilizado pa a descompone mallas, su implemen ación es
sencilla y no muy obus a pe o de bajo cos e empo al [68]. El susodicho algo i mo se basa en
ag upa una se ie de mues as en “K” conjun os di e en es, cada mues a es asociada al g upo
cuya media de alo es se ap oxime más a ella misma. La “mues a” u ilizada es una medida de
la dis ancia en e ca as adyacen es del modelo. Es a mues a se calcula como la suma de la
dis ancia geodésica (dis ancia a lo la go de la supe icie), más el ángulo dihed o (ángulo en e
las no males de las ca as).
De mane a simila se aplica ag upamien o espec al (“spec al clus e ing”) pa a segmen a
modelos 3D, se cons uye una ma iz de a inidad que con iene la p obabilidad de cada pa eja
de ca as de pe enece a la misma pa ición de la malla, y se calcula un núme o “K” ap opiado
de ec o es p opios. Más a de es os ec o es son u ilizados pa a ob ene una inclusión de las
ca as de la malla en una es e a uni a ia K-dimensional. A con inuación se aplica el algo i mo
“K-means” pa a la clasi icación sob e los pun os ob enidos en la es e a. Es e mé odo ob iene
buenos esul ados sob e mallas sencillas, pe o pa a mallas muy complicadas no p oduce
esul ados na u ales con lími es sua izados en las pa es segmen adas [69].
En [70], se p opone un mé odo de segmen ación y econocimien o de mallas que inco po a
conocimien o de mallas ya e ique adas y segmen adas y mallas no segmen adas. El mé odo
p opone un modelo CRF (“Condi ional Random Field” en inglés o Campo Alea o io Condicional)
23
que es un modelo es ocás ico u ilizado pa a e ique a secuencias de da os. Es udios e elan
que un buen CRF pa a segmen ación de mallas debe ene 2 pa es, una que mida la elación
en e la e ique a y la malla, y o a pa e que mida la consis encia en e la e ique a y su
ecindad. Además de lo an e io , se añaden al modelo é minos co espondien es a las mallas
no e ique adas. Es e modelo se u iliza pa a c ea un conjun o de en enamien o de un
clasi icado , dado que en ena conjun os g andes de da os con modelos CRF es una a ea
cos osa empo al y espacialmen e, se adop ó el mé odo “Vi ual E idence Boos ing [71]. El
mé odo ob iene esul ados sa is ac o ios, pe o dependiendo de las mallas de p ueba u ilizadas
y p oblemas especí icos como el de e ique a mallas idimensionales de se es humanos
p esen an allos.
2. 1.3.8 Mé odos de análisis espec al
Es as écnicas p oponen u iliza los alo es p opios de ma ices de inidas según la conec i idad
del g a o dual de la malla pa a segmen a la. Po ejemplo en [69] una ma iz de a inidad “W” es
de inida, cuyos elemen os son alo es en e 0 y 1, que mues an la p obabilidad de la ace a
“i” y “j” de pe enece al mismo conjun o. Con el in de de ini es os elemen os emplean la
unción de dis ancia de inida po [72] y un ke nel exponencial. Después se cons uye una
ma iz “V” cuyas columnas son los “k” ec o es p opios más g andes de la ma iz de a inidad
no malizada “Wn”, a con inuación se aplica el algo i mo “k-means” explicado an e io men e
sob e las ilas de “V”, usando como medida la dis ancia Euclidea es ánda . Cada uno de es os
ec o es co esponde á a iángulos de la malla co espondien es al mismo conjun o.
2.1.3.9 Mé odos basados en pun os c í icos
Explo an los “pun os c í icos”, que son pun os de la malla donde hay ca ac e ís icas de ipo
“salien e” y son u ilizados pa a guia la segmen ación y dis ingui los salien es en e ellos.
Los pun os de máximos locales según la unción del salien e de inido en el g a o dual de la
malla son de ec ados en [73]. Es os son ap o echados pa a iden i ica los bo des de los
salien es pa a después aplica el algo i mo de co e mínimo [74] pa a sepa a el salien e del
es o del obje o, la p incipal en aja de es e mé odo es que iden i ica co ec amen e los
salien es aún en p esencia de mucho uido, y su p incipal des en aja es que no unciona bien
en mallas que no engan salien es.
2. 1.3.10 Mé odos pa a edi icios
Apa e de las me odologías explicadas an e io men e, la bibliog a ía se cen a en la
econs ucción e iden i icación de obje os sob e nubes de pun os. Las nubes de pun os son los
da os básicos que ex aen los escáne es 3D y sob e los que se han hecho mul i ud de mé odos.
24
Se ha desa ollado un sis ema que oma como en ada una nube de pun os ep esen ando
una ciudad y un conjun o de obje os de en enamien o, y como salida da la segmen ación y
e ique ado, es deci , cada pun o de la nube es asociado con un segmen o y cada segmen o
iene una e ique a semán ica. El sis ema p ocede en cua o pasos, p ime o se gene a una lis a
de localizaciones con obje os de po encial in e és, después se p edice pa a cada una de es as
localizaciones cuales de sus pun os pe enecen al obje o y cuales al ondo de la escena, luego
una se ie de ca ac e ís icas desc ibiendo la o ma y con ex o del obje o son ex aídas pa a
inalmen e compa a los y clasi ica los según los ejemplos e ique ados de las mues as de
en enamien o [75].
Igualmen e exis en mé odos que u ilizan las nubes de pun os del escáne LIDAR (Ligh
De ec ion And Ranging) pa a econs ui ejados de edi icios. P ime o se hace un análisis de los
alo es p opios pa a cada pun o del ejado den o de su ecindad de Vo onoi, con es o se
consigue sepa a los pun os plana es de los no plana es lo que aumen a la obus ez del
algo i mo. El segundo paso consis e en usa el algo i mo bo oso de “K-medias” pa a ag upa
los pun os en segmen os del ejado según las no males de la supe icie. En el paso inal se usa
un algo i mo basado en múl iples pa ejas de líneas pa alelas y pe pendicula es pa a la
econs ucción, y ob ene así modelos opológica y geomé icamen e co ec os [41].
De la misma o ma hay écnicas que además de u iliza nubes de pun os usan o o ipo de
da os, un mé odo semiau omá ico de econs ucción de achadas combina in o mación de
nubes de pun os ob enidas po láse y o og a ías de co a dis ancia. Po un lado la ex acción
de líneas de las imágenes es muy p ecisa mien as que los pun os ob enidos po láse son más
adecuados pa a de ección de ca ac e ís icas planas. Al p incipio se usan es as ca ac e ís icas
pa a gene a un polied o que se á el modelo inicial de la achada, pos e io men e las líneas
de ec adas en las imágenes son empleadas y se compa an con las a is as del modelo pa a
e ina los polígonos. Po úl imo se seleccionan au omá icamen e ex u as de di e en es
imágenes pa a aplica las a la achada y aumen a su isibilidad. [50][76].
Po o o lado la segmen ación de modelos 3d de achadas a a és de escaneados lase ha ido
c eciendo en in e és pa a la comunidad cien í ica es os úl imos años, como en la mayo ía de
casos los elemen os de las achadas son planos, se hace p io i a io la de ección y
segmen ación de es os elemen os, pa a es e p opósi o de econs ucción, el algo i mo más
u ilizado es el algo i mo de RANSAC mencionado an e io men e, que es ima de mane a
obus a los planos incluidos po conjun os de pun os 3D como los exis en es en nubes de
pun os, en [46] se u iliza es e algo i mo y se compa a con planos ex aídos de o ma manual.
Un sis ema de de ección de en anas sob e imágenes de achadas u ilizando da os de
escáne es 3D es empleado en [77], donde se ob ienen coo denadas es é icas de un en o no
u bano, medidas de dis ancia pa a cada pun o son u ilizadas y así se calcula un umb al
adap a i o que puede usa se pa a bina iza la imagen, después se aplican ope aciones
mo ológicas de cie e (dila ación más e osión) pa a acaba con la de ección de con o nos de
cada componen e disjun a.
En cuan o a iden i icación de en anas en [78] se p opone o o mé odo pa a iden i ica las
sob e nubes de pun os ob enidas con el LIDAR. El sis ema sepa a p ime amen e los pun os 3D
del en o no de los pun os de la achada y en onces, p oyec a es os pun os en un plano 2D
25
pa alelo a la achada del edi icio. A con inuación se aplica un algo i mo de lími es y de
in e sión de pun os y en onces se segmen an las en anas eniendo en cuen a ambién
es icciones geomé icas. En es e pun o se explo a la sime ía buscando co espondencias
en e en anas y la achada del edi icio, es o consigue educi el amaño de las mues as y
acili a la segmen ación. Una ez encon adas las en anas es as se usan pa a e ina la nube
de pun os de la achada.
También se han implemen ado mé odos de segmen ación de achadas basados en g amá icas.
Es el caso de [79] donde se manipulan los da os u ilizados po los escáne es LIDAR, aplicando
p e iamen e un il o pa a educi el uido, después se hace una descomposición de
p o undidad en capas, y así se con ie en los da os 3D en da os 2.5D con lo que se educe la
complejidad. Pa a cada capa se aplica el algo i mo de segmen ación elacionando cada capa
con una g amá ica pa icula óp ima. Po úl imo se usan las o mas segmen adas pa a
ex usiona las a lo la go de los mapas de p o undidad y así se consigue la econs ucción
poligonal del edi icio.
2.2. Resumen
Los mé odos an e io men e explicados jun o con o os se de allan en la siguien e abla a modo
de esumen de odo lo explicado an e io men e.
METODO
AUTOR
CARACTERISTICAS
CRITERIO
Region
G owing
Besl and Jain
Polinomios de
ap oximación de
o den a iable,
media y cu a u a
gaussiana.
Dis ancia de los pun os
desde la supe icie
polinómica, es imaciones
de i adas de pun os
ce canos a la supe icie
polinómica de i ada.
Sapidis and Besl
Ap oximando la
supe icie
polinómica,
No males de la nube
de pun os
Dis ancia de los pun os
desde la supe icie
polinómica, O ien ación
de la no mal de los pun os
compa ada con la
di ección del eje Z
La oue e . al.
Cu a u as
p incipales
Un iángulo es añadido a
la egion basada en los
“clus e s” de cu a u as
p incipales
Zhang e . al.
Cu a u a Gaussiana
Valo de la cu a u a
gaussiana según un
umb al de inido po el
usua io
Zucke be ge e .al.
Ángulo died o de
iángulos
adyacen es.
Validación de la
con exidad basándose en
ángulos died os
Leona dis e . al.
Supe cuád icas
P omedio de e o de
32
Ilus ación 17: Ca as ecinas ( e de) a la ca a semilla de ec ada ( ojo).
Si un iángulo es ecino de o o, se calcula el p oduc o escala de sus no males. El esul ado
de es e p oduc o indica el ángulo en e ellas. Las 2 no males de inen 2 planos en un espacio
cuyo ángulo en e ellos se denomina ángulo died o.
Un ángulo pequeño o nulo, indica que los iángulos o man pa e de la misma egión plana,
mien as que un ángulo g ande indica que o man pa e de egiones di e en es. Se es ablece
un umb al o ac o de coplana idad pa a es e ángulo, de mane a que, si el ángulo calculado
pa a las no males es á po debajo de es e umb al, se asigna la misma egión a ambos
iángulos. En caso con a io, se asignan egiones di e en es. En las siguien es imágenes se
pueden e di e en es esul ados pa a el mismo iángulo, según el alo umb al que se
seleccione.
Ilus ación 18: Ca a semilla ( ojo), Ca a ecina pa a expandi la egión ( e de) y, ca as ecinas desca adas pa a la
expansión de la egión (azul).

33
Ilus ación 19: Mismo caso que el an e io pe o con un alo umb al más pequeño.
En la siguien e ilus ación se iene un ejemplo de lo explicado an e io men e, en es e caso, el
ángulo o mado po las no males ep esen adas en neg o en e la ca a semilla y uno de sus
ecinos es ce cano a ce o, ya que las no males son pa alelas, po lo que se conside a que es os
dos iángulos o man pa e de la misma ca a plana.
Ilus ación 20: T iángulos de la misma ca a plana.
En cambio la siguien e ilus ación, el ángulo en e las no males es mayo , ap oximadamen e
de no en a g ados, po lo que los iángulos se co esponde ían con ca as planas di e en es.
34
Ilus ación 21: T iángulos de ca as planas di e en es.
Una ez se han p ocesado odos los iángulos ecinos a la “ca a semilla”, se de iene el p oceso
de expansión de la egión y se pasa a busca o a “ca a semilla” pa a epe i el p ocedimien o.
El algo i mo con inua has a que no quedan más “ca as semilla” y se iene como esul ado un
conjun o de pequeñas egiones o madas po iángulos y sus ecinos co espondien es a la
misma ca a plana. Pa a ges iona es as egiones se ha u ilizado un “MFSe ”.
Un MFSe (del inglés Me ge-Find Se ) es una es uc u a de da os donde se o ganizan una se ie
de conjun os disjun os con un núme o de elemen os ijos, cada subconjun o se iden i ica po
un miemb o que es el “ ep esen an e” del g upo. Es a es uc u a con iene dos ope aciones
que la ca ac e izan:
 Combinación (Me ge): Se unen dos conjun os.
 Encon a (Find): De e mina el conjun o al que pe enece el elemen o pasado como
en ada.
Se ep esen a la es uc u a de da os como un ec o “𝑉”, donde “𝑉[𝑖]” indica el pad e del
elemen o i-ésimo.
Cada subconjun o de la es uc u a es un á bol, un á bol es un ipo de es uc u a de g a os que
se explica á más adelan e. Los nodos del á bol los elemen os del conjun o. El nodo aíz del
subconjun o es el ep esen an e del mismo. En el mé odo p opues o se conside a un nodo de
es e á bol como un iángulo y cada á bol ep esen a una ca a plana. Al hace una ope ación
“Find” se encuen a el ep esen an e de ese elemen o, que con end á un iden i icado de
colo . De es a o ma se asignan a odos los elemen o del g upo, que son iángulos, el colo
indicado po su ep esen an e, con lo que se end án odos los iángulos de la misma ca a
plana con el mismo colo .
35
Ilus ación 22: Ejemplo ep esen ación de la es uc u a de da os u ilizada.
En el mé odo desa ollado lo que ha pe mi ido la es uc u a de da os es ag upa en un mismo
conjun o es as pequeñas egiones aunque engan colo di e en e. Si dos iángulos o man
pa e de la misma ca a plana, se hace una ope ación “me ge” con los índices de los iángulos,
de es a mane a pasa án a o ma pa e del mismo conjun o en la es uc u a. Po o o lado si se
comp ueba un iángulo ecino que ya iene asignado un colo , se hace la comp obación con
sus no males y si es posi i a se buscan sus ep esen an es y se hace una ope ación “me ge” de
ambos con lo que se consigue que 2 conjun os de iángulos que enían asignados di e en es
colo es, pe o pe enecían a la misma ca a plana, aho a engan un único ep esen an e. Una
ez hecho es o se puede pasa al siguien e pun o.
3.1.3 Colo eado de las egiones.
G acias a la es uc u a de da os explicada an e io men e, se puede consul a pa a cada
iángulo el ep esen an e del conjun o al que pe enece, pa a ello se c ea un “dicciona io”.
Es a es uc u a de da os con iene pa es “cla e- alo ”, cuya ca ac e ís ica es que un alo es
accesible a a és de su cla e. Así, se c ea una es uc u a cuyas cla es son núme os en e os
que e e encian colo es, con lo que podemos asigna a un núme o de ep esen an e un colo
de e minado. Pa a consegui colo ea odos los iángulos se i e a po su lis a y se comp ueba
su ep esen an e y con es e núme o se puede comp oba su colo . Si la es uc u a no con iene
el núme o se c ea un nue o colo y se añade a la misma. De es a o ma se consigue colo ea
odos los iángulos que pe enecen a una misma ca a plana.
El colo eado pe mi e dis ingui las egiones en la isualización del esul ado del algo i mo.
36
Ilus ación 23: Resul ado de ección de ca as planas.
A con inuación se mues a el algo i mo que ealiza el mé odo explicado an e io men e.
37
𝑨𝒍𝒈𝒐𝒓𝒊𝒕𝒎𝒐 𝟏. 𝐷𝑒𝑡𝑒𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑙𝑎𝑠 𝑐𝑎𝑟𝑎𝑠 𝑝𝑙𝑎𝑛𝑎𝑠.
1: o i ϵ [0 … nº iángulos] do
2: o j ϵ [0 … núme o_ ecinos_ iángulo_i] do
3: I Vecino no iene colo asignado and
AnguloNo males( iángulo_i, ecino_j) < lími e hen
4: Asigna a ecino_j el mismo colo que iángulo_i;
5: m s.Me ge( iángulo _i.Indice, ecinos_l.Indice);
6: else
7: i Vecino ya iene colo asignado and
AnguloNo males( iángulo_i, ecinos_j) < lími e hen
8: m s.Me ge(m s.Find( iángulo_i.Indice),m s.Find( ecinos_j.Indice));
9: end i
10: end i
11: end o
12: end o
13: o i ϵ [0 … nº iángulos] do
14: m

MFSe .Find(i);
15: i Dicciona io con iene cla e “m” hen
16: iángulo _i.Colo

Colo de uel o po el dicciona io con cla e “m”;
17: else
18: Ag ega al dicciona io cla e “m” con un colo alea o io;
19: iángulo _i.Colo

Colo de uel o po el dicciona io con cla e “m”;
20: end i
21: end o
3.2 Dis inción de ca ac e ís icas
Una ez se ienen las ca as planas del obje o di e enciadas, el siguien e paso es cons ui un
“g a o opológico”, en es e caso un g a o no di igido, se de inen es os concep os a
con inuación:
 Un g a o se de ine como un pa 𝐺=(𝑉,𝐸), donde “𝑉” es un conjun o de é ices o
nodos, y “𝐸” es un conjun o de a is as o a cos que elacionan es os nodos.
 En un g a o no di igido las a is as “𝐸” son un conjun o de pa es no o denados, es deci ,
(𝑣𝑖,𝑣𝑗)≡ (𝑣𝑗,𝑣𝑖),𝑣𝑖 𝑦 𝑣𝑗 𝜖 𝑉,(𝑣𝑖,𝑣𝑗) 𝜖 𝐸 𝑦 (𝑣𝑗,𝑣𝑖) 𝜖 𝐸.
En es e caso el g a o opológico desc ibe las elaciones de ecindad en e las ca as planas
de ec adas en el paso an e io . De es a mane a en el conjun o de ca as planas “𝑃”, cada ca a
"𝑝𝑖" con iene su co espondien e nodo “𝑣𝑖” del conjun o “𝑉” de nodos del g a o. Dos é ices
“𝑣𝑖” y “𝑣𝑗” es án unidos po una a is a 𝑒 = (𝑣𝑖 ,𝑣𝑗) 𝑠𝑖 Ǝ𝑟𝜖𝑃𝑖,𝑠𝜖𝑃𝑗: 𝑃𝑖 ,𝑃𝑗 son ca as planas
unidas del obje o idimensional.

38
Se di e encian dos ipos de ca ac e ís icas, po un lado las ca ac e ís icas cónca as ales como
huecos, hendidu as o en anas y po o o lado las ca ac e ís icas con exas como salien es,
canalones, escudos o namen ales en las achadas, e c.
El g a o opológico p esen a la siguien e p opiedad: los é ices que o man las ca ac e ís icas
del modelo se unen al es o del g a o po un é ice de co e, ambién llamado pun o de
a iculación.
Un é ice de co e es de inido como aquel é ice que al qui a lo, aumen a el núme o de
componen es conexas del g a o.
Una componen e conexa de un g a o es odo aquel subg a o inducido po los é ices de una
clase de equi alencia.
Las clases de equi alencia son subconjun os en los que se di ide el conjun o o iginal, con las
p opiedades siguien es:
 Los subconjun os al uni los dan el conjun o o al.
 Los subconjun os ienen que se disjun os.
 La in e sección en e ellos debe da como esul ado el conjun o acío, es deci , los
subconjun os no compa en elemen os.
Si solo exis e una componen e conexa, o lo que es lo mismo, si odos los é ices se alcanzan
mu uamen e, se dice que el g a o es conexo. En el caso de la malla 3D que ep esen a una
achada, el “g a o opológico” siemp e a a se un g a o conexo, debido a que la malla de la
achada no a a p esen a discon inuidades, es deci , no an a exis i achadas con dos pa es
no unidas, las achadas de los edi icios se es ablecen en una sola supe icie que se iden i ica
con un único edi icio. En la siguien e imagen se mues a un ejemplo de g a o no di igido con 3
componen es conexas y sus co espondien es clases de equi alencia.
Ilus ación 24: Ejemplo de g a o con 3 componen es conexas.
39
Los é ices de co e se co esponden con ca as planas del modelo 3D que con ienen las
ca ac e ís icas que se buscan. Po ejemplo, en el caso de achadas de un edi icio, un é ice de
co e se ia la pa ed. Al elimina es e nodo del g a o, queda un nue o g a o de a ias
componen es conexas, siendo cada una de ellas una ca ac e ís ica en conc e o. Po ello al
de ec a los é ices de co e de un g a o opológico, se pueden aisla las ca ac e ís icas en
o ma de g a os (componen es conexas).
Ilus ación 25: Ejemplo de é ices de co e.
Pa a de ec a los é ices de co e de un g a o se ha u ilizado el algo i mo de Ta jan [82], que
se basa en el algo i mo DFS (“Dep h-Fi s Sea ch”, búsqueda p ime o en p o undidad) de
eco ido de g a os. La es a egia explo a sis emá icamen e las a is as del g a o, de o ma que
se isi an p ime o los é ices ecinos a los isi ados más ecien emen e. De es a o ma se a
p o undizando en el g a o, o lo que es lo mismo, se aleja cada ez más del é ice inicial. Se
con inúa con el p oceso, has a que odos los é ices alcanzables desde el é ice de la llamada
o iginal han sido descubie os, es deci , isi ados po p ime a ez.
Ilus ación 26: Ejemplo eco ido g a o u ilizando DFS, O den: 0, 4, 3, 1, 2.
El p ocedimien o a segui pa a log a es e p opósi o es la ecu si idad. Los algo i mos
ecu si os se llaman a sí mismos pa a encon a la solución al p oblema, has a que llegan a un
caso base, momen o en el cual se e o nan las llamadas y se calcula el esul ado inal.
40
El eco ido de un á bol opológico se ealiza en o ma de á bol, denominado “á bol DFS”. A
con inuación se incluyen una se ie de de iniciones elacionadas con el concep o de es uc u a
a bó ea en g a os:
 Un g a o no di igido, es un “á bol” si es conexo y acíclico.
 Un g a o 𝐺 se dice conexo si, pa a cualquie pa de é ices “𝑢” y “𝑣” en 𝐺, exis e al
menos una sucesión de é ices adyacen es que, sin epe i é ices, aya de “𝑢” a “𝑣”.
 Un g a o 𝐺 se dice que es acíclico si no con iene ciclos, es deci , si no exis en caminos
que empiecen y acaben en el mismo é ice.
 En el á bol DFS un é ice “𝑢” es pad e de o o é ice “𝑣”, si “𝑢” descub e a “𝑣” (y po
an o son nodos adyacen es en el g a o).
En un g a o cualquie a un é ice “u” es é ice de co e si se cumplen cualquie a de las
siguien es condiciones:
 “𝑢” es aíz del á bol DFS y iene al menos dos hijos.
 “𝑢” no es aíz del á bol DFS y iene un hijo “𝑣” al que ninguno de sus descendien es
es á conec ado con alguno de los ances os en el á bol DFS de “𝑢”.
Así, la búsqueda de los é ices de co e, se ealiza eco iendo el g a o con el algo i mo DFS
comp obando es as es icciones y almacenando los é ices solución.
Una ez se de ec an los é ices de co e, el siguien e paso consis e en bo a los del g a o
ac ual, en consecuencia se consigue un g a o en el que cada una de sus componen es conexas
ep esen a una ca ac e ís ica de la achada. Pa a ex ae es as componen es conexas, se usa
de nue o el algo i mo DFS, de ol iendo de o ma ecu si a los nodos que pe enecen a la
misma componen e conexa.
Pa a con inua se mues a el algo i mo u ilizado que de ec a los é ices de co e.
41
𝑨𝒍𝒈𝒐𝒓𝒊𝒕𝒎𝒐 𝟐. 𝐷𝑒𝑡𝑒𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑣é𝑟𝑡𝑖𝑐𝑒𝑠 𝑑𝑒 𝑐𝑜𝑟𝑡𝑒.
1: Ve ices_A iculacion_Aux(){
2: Inicializa cuen a de los hijos del á bol DFS
3: Se ma ca el nodo ac ual como isi ado
4: Inicializa iempo de descub imien o y alo 'low'
5: o cada nodo ecino del ac ual do
6: i ( no se ha isi ado oda ía) hen
7: Se hace hijo de “u” en el á bol DFS y lo llamamos ecu si amen e.
8: Ve ices_A iculacion_Aux( );
9: Se comp ueba si el subá bol con aíz iene conexión con algún ances o de u
10: i ( u es aíz del á bol DFS y iene 2 o más hijos) hen
11: Se añade “u” a la lis a solución.
12: end i
13: i ( Si u no es aíz y el alo low de uno de sus hijos es mayo que el alo de
descub imien o de u) hen
14: Se añade “u” a la lis a solución.
15: else
16: Ac ualiza el alo de u pa a las llamadas de los pad es
17: end i
18: end o
19: }
A con inuación se de inen “g a os de consul a”. Cada uno de ellos ecoge la con igu ación de la
o ma de un obje o. Básicamen e se a a de “g a os opológicos” de una ca ac e ís ica en
conc e o, po lo que una ca ac e ís ica queda ipi icada como un g a o de consul a. Es os
g a os se in oducen manualmen e po el usua io en la aplicación. Lo que se p e ende es
ap o echa el conocimien o que posee el usua io sob e la opología de las ca ac e ís icas,
ep esen ando és a como un g a o donde cada nodo es una de las ca as que ep esen an las
ca ac e ís icas a encon a y las elaciones en e los nodos de inen la o ma de és as. En es e
pun o, el p oblema que queda es el de compa a los g a os de las componen es conexas con
los g a os de consul a, de es a o ma se encuen an ca ac e ís icas con la misma opología que
los g a os de consul a que se han de inido. No obs an e es o no suele se su icien e pa a
dis ingui en e odas las ca ac e ís icas posibles, y se á necesa io po an o añadi
pos e io men e más es icciones.
El p oblema de compa a dos g a os se conoce o malmen e como “isomo ismo de
subg a os”, en el que se dan como en ada dos g a os “A” y “B” y se debe de e mina si “G”
con iene un subg a o que sea isomo o a “B”. Se demues a que el p oblema de isomo ismo
de subg a os es NP-comple o en [83][84].
Un “isomo ismo de g a os” es una biyección en e los é ices de los g a os que man iene sus
elaciones de adyacencia. A con inuación se de ine el concep o de unción biyec i a:
48
Ilus ación 33: Reconocimien o de iángulos/ ace as.
Seguidamen e, en la ilus ación 34, se mues a el esul ado de la de ección de las ca as planas.
Se puede ap ecia que la pa ed de la achada o ma una misma componen e, mien as que el
es o de ca ac e ís icas o man pa e de componen es di e en es.
Exis e la posibilidad de cambia el umb al que se es ablece pa a sabe si 2 iángulos
pe enecen a la misma ca a plana. El cambio de e minado po es e lími e se puede alo a en
la ilus ación 35, donde se ap ecia que una ca ac e ís ica con cu a u a se de ec a de o ma
co ec a o inco ec a en unción de es e alo umb al. Se conside a que es co ec a cuando
odas las ca as que con o man la cu a u a del obje o o man pa e de la misma ca a, es deci ,
ienen asignado el mismo colo . En cambio, se conside a inco ec a en caso con a io, al y
como se ap ecia en la ilus ación.

49
Ilus ación 34: Reconocimien o de ca as planas.
Ilus ación 35: De alle de ca as planas en ca ac e ís ica cu a.
Po úl imo se mues a el econocimien o de ca ac e ís icas donde se puede e que odas las
ca ac e ís icas o ogonales se isualizan del mismo colo , iden i icando las posiciones de las
en anas y ca ac e ís icas cónca as en la achada.
50
Ilus ación 36: Reconocimien o de ca ac e ís icas.
En es e p oceso se han u ilizado los g a os de consul a que de inen los pa ones opológicos a
busca den o de los g a os que especi ican cada ca ac e ís ica. Así, la ilus ación siguien e
mues a el ejemplo de de ec a los escalones en el modelo an e io a pa i del g a o pa ón
que los de ine. El esul ado se mues a iden i icando la ca ac e ís ica del mismo colo .
Ilus ación 37: Pa ón y ca ac e ís ica encon ada en el modelo.
51
Si compa amos es e g a o con la imagen de echa de la ilus ación 35, se puede ap ecia como
las ca as planas de los escalones o ma ían un g a o como el mos ado en la igu a an e io . Al
compa a es os g a os y encon a los iguales se colo ea oda la ca ac e ís ica del mismo colo .
52
5.-RESULTADOS
5.1 Plan eamien o
En es a sección se ealiza el análisis de los da os ob enidos al ejecu a p uebas sob e di e en es
ipos de modelos 3D. Se es udian p incipalmen e los cos es empo ales de los algo i mos y el
núme o de ca as planas o ca ac e ís icas de ec adas.
Todos los algo i mos han sido p og amados con el lenguaje “C#” y es eados sob e un
p ocesado In el Co e i7 a 2.30GHz y 4Gby es de memo ia RAM, o denado con elocidad de
p ocesamien o común hoy en día. A la is a de los esul ados, no son necesa ios equipos más
po en es pa a ob ene esul ados acep ables en cuan o a cos e empo al se e ie e.
Las p uebas ealizadas se han aplicado sob e 4 ipos de modelos di e en es. En p ime luga se
iene un g upo de “Fo mas egula es” que con ienen igu as geomé icas usuales, como una
pi ámide, un cilind o o un dodecaed o. El siguien e g upo es el de “Fo mas I egula es” que
como su nomb e indica con iene modelos i egula es y que en la mayo ía de casos p esen an
ca ac e ís icas cu as. Algunos ejemplos u ilizados como o mas i egula es son el modelo de
una pied a y el modelo de una mesa. A con inuación, el g upo de “Edi icios modelados”, que
ep esen an mallas 3D de edi icios o achadas ealizadas con p og amas de modelado. Po
úl imo se iene el g upo de “Edi icios escaneados”, que son las mallas 3D que se co esponden
con los edi icios escaneados de la ciudad de “Pie abuona”, p opo cionadas po el
Dipa amen o di A chi e u a de la Uni e si à degli S udi di Fi enze.
Pa a cada uno de los modelos a analiza se han es ablecido di e en es angos de alo es
angula es pa a el ac o de coplana idad. Es os angos an de 0 a 30, de 30 a 60, de 60 a 90 y
de 90 a 120 g ados. Pa a cada uno de es os angos se han es udiado los siguien es ac o es: en
p ime luga el cos e empo al en segundos del algo i mo que econoce los iángulos, después
el cos e de de ección de las ca as planas y a con inuación el cos e de de ección de las
ca ac e ís icas. Po úl imo, se incluye el núme o de ca as planas y el núme o de ca ac e ís icas
de ec adas.
Seguidamen e se mues an las ablas u ilizadas pa a la oma de da os. Se ha ealizado una
ba e ía de p uebas más amplia con una can idad mayo de modelos, pe o pa a es e capí ulo
solo se mues a un ejemplo de modelo de cada uno de los g upos desc i os an e io men e.
53
Fo ma Regula :
Dodecahed on
T iángulos
36
Rango Ángulo
coplana idad
Tiempo de econocimien o
de iángulos (seg.)
Tiempo de econocimien o de
ca as planas (seg.)
Tiempo de econocimien o de
ca ac e ís icas (seg.)
Ca as Planas
econocidas
Ca ac e ís icas
econocidas
0-30
0,000175476
0,00050354
0,003036499
12
1
30-60
0,000137329
0,000640869
0,002349854
12
1
60-90
0,000091552
0,000549316
0,000976563
1
1
90-120
0,000135899
0,000459671
0,001365662
1
1
Tabla 3: Da os de p ueba pa a una malla 3D que ep esen a un dodecaed o ( o ma egula ).
Fo mas I egula :
Rock
T iángulos
500
Rango Ángulo
coplana idad
Tiempo de econocimien o
de iángulos (seg.)
Tiempo de econocimien o de
ca as planas (seg.)
Tiempo de econocimien o de
ca ac e ís icas (seg.)
Ca as Planas
econocidas
Ca ac e ís icas
econocidas
0-30
0,000457764
0,008422852
0,05093384
46
1
30-60
0,000549316
0,0100708
0,04699707
2
1
60-90
0,000358582
0,01010132
0,01071167
1
1
90-120
0,000396729
0,008483887
0,01119995
1
1
Tabla 4: Da os de p ueba pa a una malla 3D que ep esen a una oca ( o ma i egula ).

54
Edi icio
Modelado:
Facade 1
T iángulos
1331
Rango Ángulo
coplana idad
Tiempo de econocimien o
de iángulos (seg.)
Tiempo de econocimien o de
ca as planas (seg.)
Tiempo de econocimien o de
ca ac e ís icas (seg.)
Ca as Planas
econocidas
Ca ac e ís icas
econocidas
0-30
0,001739502
0,01715088
1,511597
338
28
30-60
0,000671387
0,01660156
1,415344
278
29
60-90
0,000549316
0,01721191
1,12854
227
29
90-120
0,000488281
0,02248001
0,4725342
5
1
Tabla 5: Da os de p ueba pa a una malla 3D que ep esen a la achada modelada de un edi icio (edi icio modelado).
Edi icio
Escaneado:
Pie abuona_2
T iángulos
1487
Rango Ángulo
coplana idad
Tiempo de econocimien o
de iángulos (seg.)
Tiempo de econocimien o de
ca as planas (seg.)
Tiempo de econocimien o de
ca ac e ís icas (seg.)
Ca as Planas
econocidas
Ca ac e ís icas
econocidas
0-30
0,001953125
0,02050781
0,3417969
102
5
30-60
0,001464844
0,02099609
0,1982422
41
7
60-90
0,001953125
0,02246094
0,1572266
11
3
90-120
0,000976563
0,0234375
0,1494141
2
1
Tabla 6: Da os de p ueba pa a una malla 3D que ep esen a la achada escaneada de un edi icio (edi icio escaneado).
55
5.2 Análisis y conside aciones
Teniendo en cuen a el conjun o de da os o al y las p uebas ealizadas, a con inuación se
exponen las conclusiones obse adas.
Pa a analiza la bondad del algo i mo de de ección de ca as planas, se equie e con as a los
esul ados ob enidos con a modelos conocidos, de los que se sabe p e iamen e el esul ado
espe ado, es deci , el núme o de ca as planas que con iene el modelo. Pa a ello se han
u ilizado pa a el análisis polied os egula es, los cuales se conoce de an emano el núme o de
ca as planas que con ienen. Po ejemplo, se sabe que un hexaed o iene 6 ca as planas o que
un oc aed o es á compues o po 8 ca as planas.
Seguidamen e, se mues a la abla con los esul ados ob enidos. Pa a cada polied o se
mues a: el núme o de iángulos de su malla 3D, el núme o de ca as planas conocido a p io i
del polied o, el núme o de ca as planas de ec adas po el algo i mo y el alo mínimo del
ángulo de coplana idad que consigue que el algo i mo iden i ique co ec amen e las ca as
planas.
Polied o
NºT iángulos
Ca as
Planas del
polied o
Ca as Planas
De ec adas
Mínimo Ángulo de
Coplana idad pa a
de ección co ec a
Pi ámide
8
5
5
1
P isma T iangula
8
5
5
1
Hexaed o
12
6
6
1
Oc aed o
8
8
8
1
Dodecaed o
36
12
12
1
Icosaed o
20
20
20
1
Tabla 7: Da os de p ueba pa a la de ección de ca as planas sob e polied os egula es.
A la is a de es os esul ados se concluye que el mé odo, no solo econoce las ca as planas de
o ma co ec a, sino que además lo hace con un ángulo de coplana idad muy bajo, lo cual
e idencia la bondad del mé odo p opues o.
La siguien e g á ica mues a el cos e empo al del algo i mo de econocimien o de ca as
planas, calculado pa a odos los modelos 3D disponibles cuyo núme o de iángulos se
encuen e den o del ango 0 a 3000. Se e e lejada una endencia lineal en e el núme o de
iángulos y el cos e empo al, de mane a gene al a mayo núme o de iángulos, se end án
modelos con mayo núme o de de alles y po an o mayo núme o de ca as planas.
56
G á ica 1: Cos e de econocimien o de ca as planas.
El iempo que se a da en econoce las ca ac e ís icas es obse ado en la g á ica 2. Se pueden
ene en cuen a dos ac o es a la is a de los esul ados. En p ime luga , no se ap ecia una
elación di ec a en e el núme o de iángulos de la malla 3D y el iempo que se a da en
econoce las ca ac e ís icas de la misma. El cos e empo al asociado a la de ección de
ca ac e ís icas en una malla 3D iene de e minado po el núme o de ca as planas exis en es en
el modelo idimensional, que se analiza más adelan e en la g á ica 3. Es e ac o se e idencia
en la g á ica 2, donde en los angos 1000 a 1500 y 1500 a 2200, se gene an una se ie de picos
que ocu en debido a que cuando un modelo con iene un al o núme o de ca ac e ís icas
planas, el cos e empo al aumen a causando los picos de la g á ica. El segundo ac o que se
ap ecia es que con o me aumen a el ángulo de coplana idad que se es ablece, disminuye el
cos e empo al.
G á ica 2: Cos e de econocimien o de ca ac e ís icas en el modelo.
0
0,01
0,02
0,03
0,04
0,05
0,06
0 500 1000 1500 2000 2500 3000
Tiempo en segundos
Núme o de iángulos
T iangulos/Tiempo Reconocimien o de ca as planas
ángulo 0-30
ángulo 30-60
ángulo 60-90
ángulo 90-120
0
0,2
0,4
0,6
0,8
1
1,2
1,4
1,6
1,8
0 1000 2000 3000
Tiempo en segundos
Núme o de iángulos
Reconocimien o Ca ac e ís icas
Ángulo 0-30
Ángulo 30-60
Ángulo 60-90
Ángulo 90-120
57
A mayo ángulo conside ando pa a la coplana idad de los iángulos, se de ec an un meno
núme o de ca as planas, lo que se aduce en un meno núme o de nodos a u iliza po el
algo i mo de de ección de ca ac e ís icas, disminuyendo po an o el cos e empo al.
Es e hecho queda demos ado en la siguien e g á ica, en la que se ap ecia que, de mane a
gene al, con o me aumen a el núme o de ca as planas, aumen a ambién el cos e empo al. El
caso especial se da cuando el ángulo de coplana idad es de no en a g ados o mayo , ya que en
es a si uación el modelo iene un núme o muy educido de ca as planas (1 o 2 en los modelos
es eados), con lo que el cos e empo al apenas a ía en e los di e en es modelos en
compa ación con el es o de angos angula es.
G á ica 3: Relación en e el núme o de ca as planas de ec adas y el cos e de econocimien o de las ca ac e ís icas
del modelo.
Como ya se ha dicho an e io men e dos de los conjun os de modelos u ilizados du an e las
p uebas son “Fo mas Regula es” y “Fo mas I egula es”, es os modelos se han compa ado
en e sí a la ho a de de ec a ca as planas, ya que los modelos egula es ca ecen de
ca ac e ís icas y es án compues os en su mayo ía po ca as planas.
0
0,2
0,4
0,6
0,8
1
1,2
1,4
1,6
1,8
0 100 200 300 400
Tiempo segundos
Núme o de ca as planas
NºCa as Planas/Tiempo Reconoce Ca ac e ís icas
Ángulo 0-30
Ángulo 30-60
Ángulo 60-90
Ángulo 90-120
64
6.2 Ampliaciones u u as
Una de las posibles líneas de abajo u u o se ía aumen a la obus ez de los pa ones. Como
ya se ha is o an e io men e, exis en pa ones que pueden ep esen a dos obje os di e en es
po lo que se equie e de comp obaciones adicionales pa a pode dis ingui los obje os en e
sí. Ya que los “g a os de consul a” son los pa ones que u ilizamos, se pod ía do a de
in o mación adicional a los nodos de es e g a o pa a así hace cada pa ón más único, po lo
que se ía más ácil dis ingui las di e en es ca ac e ís icas exis en es.
Po o o lado, ac ualmen e los pa ones se de inen de mane a o almen e manual, a a és del
código de p og amación u ilizado, no obs an e es a a ea puede se un an o ediosa e incluso
pelig osa pa a un usua io sin nociones de p og amación, ya que pod ía esul a a al un cambio
no debido sob e el código del p og ama. Pa a soluciona es o se p opone mejo a la de inición
de los pa ones, haciendo más accesible la c eación de es os “g a os de consul a” pa a
usua ios inexpe os en la p og amación.
Una mane a de au oma iza el p oceso de c eación de los “g a os de consul a” se ía u iliza el
algo i mo desc i o en es a memo ia pa a econoce ca as planas. En luga de de ini g a os de
mane a manual, se pod ía u iliza un modelo 3D que ep esen a a una ca ac e ís ica que se
quisie a busca sob e o a malla, es deci , un pa ón. Al dispone ya de un algo i mo de
econocimien o de ca as planas que nos de ine un “g a o opológico” de una malla, se puede
explo a pa a au oma iza el p oceso de c eación de los “g a os de consul a”, pues solo se
end ía que usa la malla 3D que se quisie a u iliza como pa ón a busca y ejecu a el
algo i mo. La des en aja adica ía en onces en la capacidad que enga el usua io pa a modela
en 3D las ca ac e ís icas que se deseen encon a .
Al au oma iza es os p ocesos, el núme o de pa ones c ece ía ápidamen e, po lo que deja ía
de se e icien e ene es os ecu sos en la memo ia del o denado . Se ía más adecuado
in oduci los pa ones sob e una base de da os ex e na in oduciendo compu ación en la
“nube”, que pe mi i ía cen aliza el acceso a es os ecu sos pa a mul i ud de usua ios.

65
7.- REFERENCIAS
[1]h ps://segmen aciondeme cado. iles.wo dp ess.com/2010/11/de inicion-de-
in es igacion-de-me cados-segmen aciondeme cado-wo dp ess-com.pd
[2] Die ha d Tau z, “Segmen a ion”, De elopmen al Cell, Vol. 7, 301–312, Sep embe , 2004,
Copy igh 2004 by Cell P ess.
[3] Linda G. Shapi o and Geo ge C. S ockman (2001): “Compu e Vision”, pp 279-325, New
Je sey, P en ice-Hall.
[4] Xuehan Xiong, An onio Adan, Bu cu Akinci, Daniel Hube , “Au oma ic C ea ion o
Seman ically Rich 3D Building Models om Lase Scanne Da a”, 2013.
[5] Juan Manuel Co so Sa mien o, “PROCESOS DE SEGMENTACIÓN DE NUBES DE PUNTOS
Segmen ación y clasi icación de la ecnología de Láse Escáne Te es e TLS”, 2012.
[6] And és Ga cía Mo o, “Ap oximación a la ges ión de modelos 3D pa a el le an amien o
a qui ec ónico” 2014.
[7] "Geog aphic In o ma ion Sys ems as an In eg a ing Technology: Con ex , Concep s, and
De ini ions". ESRI. h p://www.colo ado.edu/geog aphy/gc a /no es/in o/in o.h ml. 2011.
[8] De i eddy, C. R., & Ghosh, K. (1999). Fea u e-based modeling and neu al ne wo ks-based
CAPP o in eg a ed manu ac u ing. In e na ional Jou nal o compu e In eg a ed
Manu ac u ing, 12(1), 61–74.
[9] S ee alsan, P. C., & Shah, J. J. (1992). Uni ica ion o o m ea u e de ini ion me hods.
P oceedings o he IFIP WG 5.2 Wo kingCon e ence on In elligen Compu e Aided Design, 83–
106.
[10] Luby, S. C., Dixon, J. R., & Simmons, M. K. (1986). C ea ing and using a ea u e da abase.
Compu e s in Mechanical Enginee ing, 5(3), 25–33.
[11] Hi oshi Saku ai “Volume decomposi ion and ea u e ecogni ion: Pa 1 – Polyhed al
Objec s” 1995.
[12] Emad S. Abouel Nas , Ali K. Kam ani “A new me hodology o ex ac ing manu ac u ing
ea u es om CAD sys em” 2006.
[13] M. A ene e al. “Mesh segmen a ion – A compa a i e s udy” 2006
h p://cgm. echnion.ac.il/Compu e -G aphics-
Mul imedia/Publica ions/Pape s/2006/206_Mesh_segmen a ion_A_compa a i e_s udy.pd
[14] A iel Shami “A Su ey on Mesh Segmen a ion Techniques” 2007.
[15] Salem Saleh Al-am i, N.V.Kalyanka and Khami ka S.D, “Image Segmen a ion by Using
Th eshold Techniques”, Jou nal O Compu ing, Volume 2, Issue 5, May 2010.
66
[16] H. G. Kaganami and Z. Beij, “Region based de ec ion e sus edge de ec ion,” IEEE
T ansac ions on In elligen In o ma ion Hiding and Mul imedia Signal P ocessing, pp. 1217-
1221, 2009.
[17] S. Kullback, In o ma ion heo y and s a is ics, Wiley, New Yo k, 1959.
[18] I. Ka oui, R. Fable , J. Bouche , and J. Augus in, “Unsupe ised egion-based image
segmen a ion using ex u e s a is ics and le el-se me hods,” in P oc. WISP IEEE In e na ional
Symposium on In elligen Signal P ocessing, 2007, pp. 1-5,2007.
[19] Y. M. Zhou, S. Y. Jiang, and M. L. Yin, “A egion-based image segmen a ion me hod wi h
mean-shi clus e ing algo i hm,” in P oc. Fi h In e na ional Con e ence on Fuzzy Sys ems and
Knowledge Disco e y, 2008, pp. 366-370
[20] Kons an inos G. De panis “Mean Shi Clus e ing”, Augus 15, 2005
[21] C. Cigla and A. A. Ala an, “Region-based image segmen a ion ia g aph cu s,” in P oc. 15 h
IEEE In e na ional Con e ence on Image P ocessing, 2008, pp. 2272-2275.
[22] S. Lakshmi and D. V. Sanka ana ayanan, “A s udy o edge de ec ion echniques o
segmen a ion compu ing app oaches,” IJCA Special Issue on “Compu e Aided So Compu ing
Techniques o Imaging and Biomedical Applica ions” CASCT, 2010.
[23] X. Yu and J. Yla-Jaaski, “A new algo i hm o image segmen a ion based on egion g owing
and edge de ec ion,” in P oc. IEEE In e na ional Sympoisum on Ci cui s and Sys ems, pp. 516-
519, 1991.
[24] Sla o Wesolkowski and Paul Fiegu h, “A ma ko andom ields model o hyb id edge-an
egion-based colo image segmen a ion”, 2002
[25] Ying-Tung Hsiao, Cheng-Long Chuang, Joe-Ai Jiang, and Cheng-Chih Chien, “A Con ou
based Image Segmen a ion Algo i hm using Mo phological Edge De ec ion”, 2005 IEEE
In e na ional Con e ence on Sys ems, Man and Cybe ne ics Waikoloa, Hawaii Oc obe 10-12,
2005.
[26] Dong Hu Xianzhong Tian, “A Mul i-di ec ions Algo i hm o Edge De ec ion Based on Fuzzy
Ma hema ical Mo phology”, 2006.
[27] Ka maka , G. C. and Dooley, L. S. (2001). “A gene ic uzzy ule based echnique o image
segmen a ion.” In: IEEE In e na ional Con e ence on Acous ics, Speech and Signal P ocessing
(ICASSP ’01), 7-11 May 2001, Sal Lake Ci y, U ah.
[28] A. S. Pedneka and I. A. Kakadia is, “Image segmen a ion based on uzzy connec edness
using dynamic weigh s,” IEEE T ansac ions on Image P ocessing, ol. 15, pp. 1555-1562, 2006.
[29] L. Yaju, Z. Baoliang, Z. Li, L. Dongming, C. Zhenjiang, and L. Lihua, “Resea ch on image
segmen a ion based on uzzy heo y,” in P oc. WRI Wo ld Cong ess on Compu e Science and
In o ma ion Enginee ing, 2009, pp. 790-794.
67
[30] James C.Bezdek, Robe Eh lich, William Full , “FCM: THE FUZZY c-MEANS CLUSTERING
ALGORITHM” 1984
[31] Ma in Hagan, “Neu al Ne wo k Design”, Cou se Announcemen , 2007.
[32] Simon Haykin, “Neu al Ne wo ks, A comp ehensi e ounda ion”, P en ice Hall.
[33] D. J. E ans and L. P. Tay, "Fas Lea ning A i icial Neu al Ne wo ks o con inuous inpu
applica ions," Kybe ne es, ol. 24, pp. 11-23, 1995.
[34] X. Zhang and A. L. P. Tay, “Fas lea ning a i icial neu al ne wo k (FLANN) based colo
image segmen a ion in RGBSV clus e space,” in P oc. In e na ional Join Con e ence on Neu al
Ne wo ks, 2007, pp. 563-568.
[35] C.L. Chang and Y.T. Ching, “ Fuzzy Hop ield neu al ne wo k wi h ixed weigh o medical
image segmen a ion ” Op ical Enginee ing, ol. 41, pp. 351-358, 2002.
[36] F. M. Kazemi, M. R. Akba zadeh, T. S. Raha i, and H. Rajabi, “Fas image segmen a ion
using C-means based Fuzzy Hop ield neu al ne wo k,” in P oc. Canadian Con e ence on
Elec ical and Compu e Enginee ing, 2008, pp. 001855-001860.
[37] B ian Taylo , Alpe Ay aci, A inash Ra ichand an, and S e ano Soa o “Seman ic Video
Segmen a ion F om Occlusion Rela ions Wi hin a Con ex Op imiza ion F amewo k” 2013.
[38] P. Felzenszwalb and D. Hu enloche . “E icien g aph-based image segmen a ion”. IJCV,
59(2), 2004.
[39] Ma hias G undmann, Vi ek Kwa a, Mei Han, I an Essa, “E icien Hie a chical G aph-
Based Video Segmen a ion”, 2010.
[40] John S. Bo eczky and Lynn D. Wilcox, “Hidden Ma ko Model F amewo k o Video
Segmen a ion Using Audio and Image Fea u es”, 1998.
[41] Apa aji han Smpa h and Jie Shan “Segmen a ion and Recons uc ion o Polyhed al
Building Roo s F om Ae ial Lida Poin Clouds” 2010.
[42] R.O. Duda and P.E.Ha , “Use o he Hough ans o ma ion o de ec lines and cu es in
pic u es”, Commun. ACM, ol. 15, no. 1, pp. 11-15, Jan. 1972.
[43] G. Vosselman and S. Dijkman, “3D building model econs uc ion om poin clouds and
g ound plans,” In . A ch. Pho og amm. Remo e Sens., ol. 34, no. 3/W4, pp. 37–43, 2001
[44] J. O e by, L. Bodum, E. Kjems, and P. M. Iisoe, “Au oma ic 3D building econs uc ion om
ai bo ne lase scanning and cadas al da a using Hough ans o m,” In . A ch. Pho og amm.
Remo e Sens., ol. 35, p . B3, pp. 296–301, 2004
[45] M. Fischle and R. Bolles, “Random sample cosenus: A pa adigm o model i ing wi h
applica ions o image analysis and au oma ed ca og aphy”, Commun. ACM, ol. 24, no. 6, pp.
381-395, 1981.
68
[46] Hakim Boulaassal, Tania Landes, Pie e G ussenmeye , Fayez Ta sha-Ku di.”Au oma ic
segmen a ion o building acades using Te es ial Lase Da a.” ISPRS Wo kshop on Lase
Scanning 2007 and Sil iLase 2007, Sep 2007, Espoo, Finland. pp.65-70.
[47] Philipp Jenke, Bas ian K ¨uckebe g, Wol gang S aße , “Su ace Recons uc ion om Fi ed
Shape P imi i es”, 2008.
[48] Hai Huang and Claus B enne , “Rule-based Roo Plane De ec ion and Segmen a ion om
Lase Poin Clouds”, 2011.
[49] Apa aji han Sampa h and Jie Shan, “Segmen a ion and Recons uc ion o Polyhed al
Building Roo s F om Ae ial Lida Poin Clouds”, 2010.
[50] Shi Pu and Geo ge Vosselman, “Building Facade Recons uc ion by Fusing Te es ial Lase
Poin s and Images”, 2009.
[51] B uno Kewi z Dema chi, Felipe Pilon, “Canny Edge De ec o ”.
[52] William S Noble , “Wha is a suppo ec o machine?”, NATURE BIOTECHNOLOGY
VOLUME 24 NUMBER 12 DECEMBER 2006
[53] Rusu, R.B. Blodow, N. ; Ma on, Z.C. ; Bee z, M., “Close- ange scene segmen a ion and
econs uc ion o 3D poin cloud maps o mobile manipula ion in domes ic en i onmen s”,
2009.
[54] Ruwen Schnabel, Raoul Wessel, Roland Wahl, Reinha d Klein”Shape Recogni ion in 3D
Poin -Clouds”, 2008.
[55] Colin Smi h, On Ve ex-Ve ex Meshes and Thei Use in Geome ic and Biological
Modeling, h p://algo i hmicbo any.o g/pape s/smi hco.dis2006.pd
[56]B uce G. Baumga , Winged Edge Polyhed on ep esen a ion.
h p://www.d ic.mil/d ic/ / ull ex /u2/755141.pd
[57] Besl, P. J.; Jain, R.: “Segmen a ion h ough Va iable-O de Su ace Fi ing” , IEEE PAMI,
10(2), 1988, 167-192.
[58] Viei a, M.; Shimada, K.: “Su ace mesh segmen a ion and smoo h su ace ex ac ion
h ough egion g owing”, Compu e -Aided Geome ic Design, 22(8), 2005, 771-792.
[59] Zhang, Y.; Paik, J.; Koschan, A.; Abidi, M. A.: “A simple and e icien algo i hm o pa
decomposi ion o 3D iangula ed models based on cu a u e analysis”, P oc. In l. Con . on
Image P ocessing, 2002, 273-276.
[60] Mangan, A. P.; Whi ake , R. T.: “Pa i ioning 3D su ace meshes using wa e shed
segmen a ion”, IEEE T ansac ions on Visualiza ion and Compu e G aphics, 5(4), 1999, 308-
321.
[61] Zucke be ge , E.; Tal, A., Shla man, S.: “Polyhed al su ace decomposi ion wi h
applica ions”, Compu e s G aphics, 26(5), 2002, 733-743.
69
[62] Page, D. L.; Koschan, A.; Abidi, M.: “Pe cep ion-based 3D iangle mesh segmen a ion
using as ma ching wa e sheds”, In P oc. o Compu e Vision and Pa e n Recogni ion, 2003,
27-32.
[63] L. De Flo iani, “A g aph based app oach o objec ea u e ecogni ion”, 1987.
[64] Ma e a , M., Kashyap, R., “Geome ic easoning o ecogni ion o h ee-dimensional
objec ea u es”, 1990.
[65] Wu, K.; Le ine, M. D.: 3D Pa Segmen a ion Using Simula ed Elec ical Cha ge
Dis ibu ions, IEEE T ansac ions on Pa e n Analysis and Machine In elligence, 1997, 1223-
1235.
[66] Li, X.; Toon, T. W.; Huang, Z.: Decomposing polygon meshes o in e ac i e applica ions,
SI3D, 2001, 35-42.
[67] Shla man, S.; Tal, A.; Ka z, S.: Me amo phosis o polyhed al su aces using decomposi ion,
Eu og aphics,2002, 219-228.
[68] Ch is T alie, h p://www.c alie.com/Teaching/MeshSeg/
[69] Liu, R.; Zhang, H.: Segmen a ion o 3D meshes h ough spec al clus e ing, Paci ic
Con e ence on Compu e G aphics and Applica ions, 2004, 298–305. REPETIDO
[70] Jiajun L , Xinlei Chen, Jin Huang, Hujun Bao, “Semi-supe ised Mesh Segmen a ion and
Labeling”, 2012.
[71] Lin Liao, Tanzeem Choudhu y, Die e Fox, Hen y Kau z, “T aining Condi ional Random
Fields using Vi ual E idence Boos ing”, P oc. o he In e na ional Join Con e ence on A i icial
In elligence (IJCAI), 2007
[72] Ka z, S.; Tal, A.: Hie a chical Mesh Decomposi ion Using Fuzzy Clus e ing and Cu s, ACM
T ans. on G aphics, 22(3), 2003, 954-961.
[73] Lin, H. S.: Liao, H. M.: Lin, J.: Visual Salience-Guided Mesh Decomposi ion, IEEE In .
Wo kshop on Mul imedia Signal P ocessing, Siena (ITALY), 2004, 331-334.
[74] Ka z, S.; Lei man, G.; Tal, A.: Mesh Segmen a ion using Fea u e Poin and Co e Ex ac ion,
The Visual Compu e , 21(8-10), 2005, 649-658.
[75] Aleksey Golo inskiy, Vladimi G. Kim, Thomas Funkhouse , “Shape-based Recogni ion o
3D Poin Clouds in U ban En i onmen s”.
[76] Yangyan Li, Qian Zheng, And ei Sha , Daniel Cohen-O , Baoquan Chen, Niloy J. Mi a. “2D-
3D Fusion o Laye Decomposi ion o U ban Facades”, 2011.
[77] Ali, Haide ; Ahmed, Bashee ; Paa , Ge ha d, “Robus Window De ec ion om 3D Lase
Scanne Da a”, 2008.
[78] A. K. Aijazi, P. Checchin and L. T assoudaine, “Au oma ic Dec ec ion and Fea u e
Es ima ion o Window Fo Re ining Building Facades in 3D U ban Poin Clouds”, 2014.

70
[79] Guowei Wana, And ei Sha , “G amma -based 3D acade segmen a ion and
econs uc ion”, 2012.
[80] Alexande Aga hos, Ioannis P a ikakis, S a os Pe an onis, Nikolaos Sapidis and Philip
Aza iadis “3D Mesh Segmen a ion Me hodologies o CAD applica ions”
[81] Ken on McHen y and Pe e Bajcsy, “An O e iew o 3D Da a Con en , File Fo ma s and
Viewe s”, 2008
[82] Hopc o , J.; Ta jan, R. (1973). "Algo i hm 447: e icien algo i hms o g aph
manipula ion". Communica ions o he ACM 16 (6): 372–378.
[83] Wegene , Ingo (2005), Complexi y Theo y: Explo ing he Limi s o E icien Algo i hms,
Sp inge , p. 81.
[84] de la Higue a, Colin; Janode , Jean-Ch is ophe; Samuel, Émilie; Damiand, Guillaume;
Solnon, Ch is ine (2013), "Polynomial algo i hms o open plane g aph and subg aph
isomo phisms", Theo e ical Compu e Science 498: 76–99.
[85] J. R. ULLMAN, “An algo i hm o Subg aph Isomo phism”.1976
[86] Jinsoo Lee, Wook-Shin Han, Romans Kaspe o ics, Jeong-Hoon Lee, “An In-dep h
Compa ison o Subg aph Isomo phism Algo i hms in G aph Da abases”, 2012.