Un algo i mo en iempo eal pa a e ique ado de
componen es conec ados en imágenes
Elisa Cal o
Depa amen o de Elec ónica y Elec omagne ismo
Uni e sidad de Se illa
Se illa, España
cal [email protected]
Piedad B ox, San iago Sánchez-Solano
Ins i u o de Mic oelec ónica de Se illa (IMSE-CNM)
Consejo Supe io de In es igaciones Cien í icas
Se illa, España
b ox, san [email protected]
Resumen—Es a comunicación p esen a un algo i mo de dos
pasadas pa a el e ique ado en iempo eal de los componen es
conexos en una imagen. El algo i mo p opues o es una buena
opción en e a o as al e na i as de dos y múl iples pasadas ya
que ha sido diseñado conside ando que su implemen ación en
FPGAs o ezca un buen comp omiso en e ecu sos ocupados y
elocidad de ope ación. Se desc iben dos implemen aciones
ha dwa e de es e algo i mo, cuyo desa ollo se ha lle ado a cabo
siguiendo un lujo de diseño basado en la he amien a Sys em
Gene a o de Xilinx.
I. INTRODUCCIÓN
Cada ez con más ecuencia es necesa ia la in eg ación de
sis emas de isión po compu ado en disposi i os especí icos
y sis emas empo ados (mó iles, PDAs, edes de senso es,
e c.). Las limi aciones que p esen an es os disposi i os en
cuan o a consumo de po encia y capacidad de cálculo y
almacenamien o, así como la necesidad de ope ación en
iempo eal de las aplicaciones donde se u ilizan, obligan a
lle a a cabo una e isión de los algo i mos exis en es con el
in de adap a su implemen ación a las ca ac e ís icas de las
pla a o mas eme gen es.
Es e p oceso de adap ación es especialmen e impo an e en
los algo i mos de e ique ado de componen es conexos o
algo i mos CCL (Connec ed Componen Labeling), ya que
es os p ocedimien os cons i uyen un paso in e medio en e las
a eas de a amien o de imágenes a bajo y al o ni el, como se
ilus a en el sis ema de isión gené ico mos ado en Fig. 1.
En es e abajo se desc ibe el desa ollo de un nue o
algo i mo CCL pa a el e ique ado de imágenes co ec amen e
p ep ocesadas, así como su implemen ación e icien e sob e
FPGAs (en é minos de ecu sos y/o elocidad). En el p oceso
de diseño se ha seguido una me odología basada en Sys em
Gene a o , una he amien a de Xilinx in eg ada en el en o no
Ma lab/Simulink que, al acili a la ealización de odas las
e apas de diseño bajo un mismo ma co de e e encia, ha
pe mi ido aco a el iempo de desa ollo de las dis in as
implemen aciones.
La es uc u a de la comunicación es la siguien e. En la
Sección II se e isan algunos concep os básicos y los
p incipales ipos de algo i mos CCL exis en es en la li e a u a.
La Sección III se cen a en el análisis de un ipo conc e o de
algo i mo, los denominados algo i mos CCL de dos pasadas, y
los p oblemas que p esen a su implemen ación. La Sección IV
ecoge la p opues a de un nue o algo i mo que minimiza el
p incipal p oblema de los mé odos an e io es. En la Sección V
se mues an los esul ados ob enidos en simulación con 250
imágenes usadas habi ualmen e en aplicaciones de isión y se
compa an con los p opo cionados po un algo i mo clásico. La
Sección VI desc ibe algunos de alles de la implemen ación y
la me odología de diseño seguida. Las conclusiones del
abajo se esumen en la Sección VII.
II. ESTADO DEL ARTE DE LOS ALGORITMOS CCL
Los algo i mos CCL ealizan la asignación de un
iden i icado único a cada conjun o conexo de píxeles con
unas mismas p opiedades den o de la imagen. Es e abajo se
cen a en algo i mos que, pa iendo de una imagen bina ia (B),
an analizando conec i idades en e píxeles si uados en un
en o no o mado po cua o (N4) u ocho ecinos (N8), de
o ma que, al inal, dos píxeles, p y q, pe enece án a un
mismo componen e cuando ambos se conside en pa e del
p ime plano (o 'Fo eg ound') o del ondo ( ambién llamado
'Backg ound') y exis a un camino de píxeles del mismo ipo
en e ellos, es deci , cuando se e i ique (1), donde S es un
subconjun o de píxeles de la imagen bina ia B.
Es e abajo ha sido inanciado po los p oyec os: MOBY-DIC FP7-IST-
248858 (www.mobydic-p ojec .eu) de la Comunidad Económica Eu opea,
TEC2008-04920 del Minis e io de Ciencia e Inno ación de España y P08-
TIC-03674 de la Jun a de Andalucía (con sopo e FEDER).
Figu a 1. Sis ema de isión gené ico
{
( ) }
La Fig. 2 mues a un ejemplo de e ique ado de una imagen
donde puede comp oba se cómo el núme o de componen es
encon ados a ía en unción de la conec i idad conside ada.
Como consecuencia de la impo ancia de los algo i mos de
CCL, desde la década de los 60 se han in e ido muchos
es ue zos en el a ance y desa ollo de los mismos. Aunque
exis en a ios c i e ios que pe mi en ca aloga los dis in os
p ocedimien os, como la egula idad en el acceso a memo ia o
la o ma de ep esen ación de la imagen, esul a habi ual
ep esen a la imagen como un a ay bidimensional y
es ablece una clasi icación a endiendo al núme o de ba idos
que se ealizan de la misma, en endiendo como al la
explo ación de odos los píxeles independien emen e del o den
que se siga pa a ello. De es e modo, podemos encon a
algo i mos:
 De una pasada (one-scan): Son algo i mos en los que
se eco e la imagen una sola ez. Los accesos
i egula es y alea o ios a las es uc u as de da os que
almacenan la imagen o las e ique as asignadas, y la
di icul ad pa a p edeci los iempos de du ación de los
mé odos, son los p incipales incon enien es de es e
ipo de algo i mos, en e los que se encuen an el de
azado de con o no p esen ado po Chang en 2003 [1]
o el de as e -scan p esen ado po Bailey en 2007 [2].
 De múl iples pasadas (mul i-scan): Realizan a ios
ba idos de la imagen (no malmen e al e nos, de
a iba abajo y de izquie da a de echa, y de abajo a
a iba y de de echa a izquie da), accediendo a
memo ia de o ma egula . El iempo de ejecución del
p ocedimien o depende á de la disposición de los
píxeles en cada imagen, po lo que no es posible
es ablece , a p io i, una du ación del mé odo en cada
caso. Su implemen ación so wa e y ha dwa e es más
sencilla que la de algo i mos de o os g upos. En e
ellos se pueden des aca los abajos p esen ados po
Ha alick en 1981 [3] y Suzuki en 2000-2003 [4], [5].
 De dos pasadas (doble-scan): Son los mé odos que
lle an a cabo dos ba idos de la imagen. No malmen e
el p ime o pe mi e un e ique ado empo al de la
misma, mien as que el segundo posibili a la
asignación de las e ique as de ini i as a cada píxel.
Suelen accede a memo ia de o ma egula y usa una
o a ias ablas pa a almacena las equi alencias en e
e ique as dis in as asignadas de o ma empo al a un
mismo componen e. De hecho, las es uc u as de
da os usadas pa a almacena es as equi alencias en e
e ique as (que han e olucionado desde ma ices de
adyacencia o es uc u as de n- uplas [6] has a
es uc u as ec o iales [7] y ablas asocia i as [8]), los
algo i mos empleados pa a esol e las equi alencias
y el ins an e en el cual end á luga esa esolución,
ca ac e izan las dis in as al e na i as p opues as en la
li e a u a.
Muchos abajos publicados en es a línea se cen an
ambién en busca una solución óp ima al p oblema de
explo ación de ecinos, con el in de minimiza el
núme o de accesos a memo ia [8]-[10].
Es e ipo de algo i mos son, en gene al, más di íciles
de implemen a en ha dwa e que los de múl iples
pasadas, su iempo de ejecución es ambién ele ado y
dependien e de la complejidad de la imagen a a a y
pueden p esen a , con de e minadas es uc u as de
memo ia, solapamien os y pé didas de e ique as. Sin
emba go, en e a aquellos, p esen an la cla a en aja
de que pe mi en es ablece la du ación conc e a del
mé odo.
Es impo an e menciona que muchos de los algo i mos
publicados en los úl imos años in oducen algún ipo de
pa alelismo en las es uc u a de da os y/o en los elemen os de
p ocesado. Es as écnicas, basadas en in es igaciones iniciadas
du an e los 70 y los 80 en las cuales se diseña on e
implemen a on algo i mos sob e a qui ec u as masi amen e
pa alelas (ej. [11]- [16]) pe mi en acele a la ejecución a cos a
de un inc emen o del á ea ocupada del disposi i o, lo que se
aduce en la imposibilidad de abaja con amaños de imagen
mayo es y en el uso, en ocasiones, de memo ias ex e nas (ej.
[17]- [20]).
Figu a 2. Concep o de conec i idad cuando se conside a un en o no
de ecindad de 4 píxeles (a) u 8 píxeles (b). El a ay de píxeles
conside ados en cada caso ( ambién llamado másca a) se mues a en
la esquina supe io de echa de cada ejemplo
III. ALGORITMOS CCL DE DOS PASADAS
Los algo i mos que se adap an mejo a una
implemen ación ha dwa e en la que la imagen a a llega
como un lujo con inuo de píxeles son los algo i mos de dos
pasadas del ipo as e -scan, ya que la o ma de acceso a
memo ia suele se egula y es ablecen una du ación ini a del
p ocedimien o.
A. Algo i mo gené ico
Es e ipo de algo i mos comienzan ealizando un p ime
ba ido de la imagen, en el que se asignan e ique as empo ales
a los píxeles y se iden i ican las posibles equi alencias que
puedan p oduci se. La exp esión ma emá ica que pe mi e
desc ibi la e ique a empo al asignada al píxel (x,y) du an e el
p ime ba ido es la siguien e:
( ) {
( )
{( ) } ( )
 
donde:
 FB son los píxeles que cons i uyen el ondo de la
imagen bina ia (píxeles en neg o con alo '0') y FO
son los co espondien es al p ime plano (píxeles en
blanco con alo '1'),
 M es la en ana que es ablece el c i e io de
conec i idad en e píxeles,
 m inc emen a á su alo (m=m+1) cada ez que se
e i ique la condición {( ) } ( ) ,
 L es la e ique a empo al asignada inalmen e al píxel
(x,y). Es a e ique a ue asignada ya a alguno de los
píxeles ecinos analizados. La o ma en que se
de e mina su alo es di e en e en los dis in os
algo i mos p opues os.
Una ez se concluye el p ime ba ido, o solapado con es e
o al o pa cialmen e, se ealiza á la esolución de la abla de
equi alencias. En la segunda pasada se u iliza la in o mación
de la abla de equi alencias pa a lle a a cabo la sus i ución de
las e ique as empo ales po pe manen es.
En cuan o a ecu sos, a di e encia de los algo i mos mul i-
scan, la implemen ación ha dwa e de un algo i mo de es e ipo
equie e únicamen e una memo ia pa a almacena las
equi alencias en e e ique as, ya que las e ique as empo ales
asignadas a cada píxel du an e el p ime ba ido, que se án
necesa ias de nue o en la ase de sus i ución, pod án ol e a
se calculadas du an e es a ase u ilizando la misma ci cui e ía
empleada en la ase an e io [18].
Como se ha comen ado al es ablece la clasi icación de los
algo i mos CCL, exis en di e en es p opues as pa a la
implemen ación de la memo ia de equi alencias. De odas
ellas, las es uc u as ec o iales son las que pe mi en alcanza
un comp omiso mejo en e el consumo de memo ia y el cos e
de p ocesamien o. Sin emba go, p esen an un incon enien e:
la posible pé dida de equi alencias.
B. P oblema de pé dida de equi alencias y su e aluación
Se p oducen pé didas de equi alencias cuando se
sob esc iben las posiciones de memo ia de la abla de
equi alencias.
El algo i mo de doble-scan que se desc ibe a con inuación
co esponde a una implemen ación clásica u ilizando es e ipo
de es uc u a de memo ia. Su análisis pe mi e explica el
p oblema de pé didas de equi alencia y se á usado en es e
abajo pa a es ablece compa aciones con la solución
p opues a. Dicho algo i mo, al cual llama emos 'algo i mo 1',
p esen a las siguien es ca ac e ís icas:
 E ique a asignada en la p ime a pasada, si el píxel es
blanco y no es una nue a e ique a:
 [{ ( ) ( ) }]
 Ac ualización de la abla de equi alencia con cada
equi alencia encon ada:
([{ ( ) ( ) }])
[{ ( ) ( ) }] (4)
 Modo de esolución de la abla: T as el p ime scan,
se eco e la abla de equi alencias desde la p ime a
posición has a la úl ima. Pa a cada en ada, si la
di ección de en ada es di e en e de su equi alencia se
ac ualiza dicha en ada en la abla de acue do con:
( )
( ) ( ( )) (5)
En es e mé odo, conside ando una conec i idad 4, se
dis inguen dos ipos de pé didas:
 Simples: Se p oducen cuando exis en dos pa es
equi alen es que compa en uno de los elemen os del
pa siendo el elemen o compa ido el de más al o
alo de en e las es e ique as. Pueden da se en una
ila o en ilas di e en es. Va ias equi alencias en e
e ique as pueden enlaza se ( o mando una cadena) lo
que impide que puedan e i a se es as pé didas de una
o ma sencilla.
 Múl iples: Se p oducen cuando exis en más de dos
pa es equi alen es que compa en uno de los
elemen os del pa , siendo el elemen o compa ido el
de más al o alo de en e los conside ados.
La Fig. 3 ilus a casos de pé didas simples (en una ila (a)
o en e ilas (b)) y múl iples.
Pa a analiza con mayo p o undidad con qué ecuencia se
p oducen pé didas de equi alencias, se c ea on ba e ías de
imágenes pa ón con conca idades, con exidades y escale as
sucesi as y di e en e o den de apa ición de las e ique as
asignadas. Las simulaciones ealizadas con es as imágenes
mues an cómo el po cen aje de casos en los que exis en
pé didas es muy ele ado. Conc e amen e, con pa ones con
conca idades en una misma ila (Fig. 4 (a)) hay pé didas en un
66,7 % de los casos, con pa ones escale a c ecien e hay
pé didas en un 66,7% de los casos (Fig. 4 (b)) y con pa ones
con con exidades que compa en una columna (Fig. 4 (c))
ocu en pé didas en un 50% de los casos.
IV. ALGORITMO PROPUESTO
Con el obje i o de educi las pé didas de equi alencias y
ap o echa las en ajas que p opo ciona es e ipo de
algo i mos de dos pasadas, se ha p opues o una modi icación
sob e el ‘Algo i mo 1’. La e ique a asignada en la p ime a
pasada (si el píxel es blanco y no es una nue a e ique a) y la
ac ualización de la abla de equi alencias se ha á de acue do a:
 [{ ( ( )) ( ) }]
([{ ( ) ( ) }])
[{ ( ( )) ( ) }] (7)
Es deci , en luga de asigna la e ique a mínima de en e
las ecinas, se asigna el mínimo de en e las equi alencias de
las e ique as ecinas, al igual que se p opone en [5]. Las
en adas de la abla de las e ique as del en o no de ecindad se
ac ualizan ambién con ese mismo alo . La o ma en la que se
lle a a cabo la esolución de la abla de equi alencias se
man iene con espec o al ‘Algo i mo 1’.
Al analiza la salida de es e algo i mo con las dis in as
imágenes de las ba e ías pa ón, se comp ueba que con es e
mé odo se eliminan las pé didas múl iples y las simples que
ienen luga en una misma ila, además de educi se las
pé didas simples que ienen luga en e ilas (el po cen aje de
e o desciende del 66,7% al 33%). Es o es debido a que se
e i an las pé didas que se p oducen cuando la equi alencia del
elemen o compa ido sea meno , al p oduci se la sob esc i u a,
que la del o o elemen o del segundo pa equi alen e ( an o si
se ha modi icado su alo di ec amen e como si se ha hecho a
a és de una cadena con o os pa es).
V. RESULTADOS DE SIMULACIÓN CON IMÁGENES REALES
A. Imágenes
Pa a e alua la bondad y aplicabilidad del mé odo
p opues o se han ealizado una se ie de simulaciones con
a ios g upos de imágenes eales u ilizando las he amien as
del en o no Ma lab. Las imágenes, omadas de las bases de
da os de la USC-SIPI [21] y el Be keley Compu e Vision
G oup [22], han sido seleccionadas in en ando aba ca el
mayo ango posible en cuan o a emas, pa a comp oba la
aplicabilidad del mismo en dis in os campos: medioambien e
(animales, paisajes), segu idad (pe sonas), medicina (células),
e c.), y di icul ad, con el in de e i ica la calidad del
e ique ado (pa a ello se han seleccionado imágenes de ex u as
e imágenes aé eas).
Pa a aplica los algo i mos sob e es as imágenes, ue
necesa ia la ealización de dis in as ope aciones de
p ep ocesado sob e las mismas: con e siones de colo
(modelo RGB) a ni eles de g is, umb alizaciones median e el
mé odo de O su y dila aciones de bo des (Fig. 5).
B. Medidas ealizadas
La “calidad” del algo i mo se midió median e el cálculo de
los siguien es alo es:
 E o absolu o (E o A): Di e encia en el núme o de
componen es conexos encon ados con espec o a los
esul ados p opo cionados po la ins ucción 'bwlabel'
de Ma lab.
 E o ela i o (E o R): E o absolu o come ido en
cada imagen di idido po el núme o o al de
componen es e ique ados en cada caso.
C. Resul ados ob enidos
Los esul ados ob enidos, esumidos en la Tabla I, e lejan
que el po cen aje de imágenes en las cuales se come ió e o es
en el e ique ado descendió de un 55-75% con el 'Algo i mo 1'
a un 6-10% con el algo i mo p opues o. Es e da o, unido a que
el e o medio que se come e es en el peo de los casos de 14
e ique as en el algo i mo p opues o en e a 120 e ique as en el
'Algo i mo 1', y a que el e o ela i o máximo come ido con
el algo i mo p opues o es de 1,07% (en imágenes de ex u as),
pe mi e a i ma que la calidad del algo i mo p opues o es
buena y mejo que la de un algo i mo ípico de es e ipo.
Además, hay que ene en cuen a que las imágenes con las que
Figu a 3. Ejemplos de pé didas simples y múl iples (a) Imagen. (b)
E ique ado empo al. (c) E olución de la abla de equi alencias
du an e el ba ido inicial (izq. inicial, de . inal). En ojo, los
cambios en cada ciclo. En azul, los casos en los que se
sob eesc iben equi alencias en e e ique as. (d) E ique ado inal
Figu a 4. Ejemplos de pa ones analizados en el es udio de
pé didas de equi alencias (a) Conca idades sucesi as en una ila
(b) Escale a c ecien e (c) Con exidades sucesi as en una e ical
se come en más e o es han sido seleccionadas po su
di icul ad pe o no malmen e los algo i mos de e ique ado no
se aplican a esas imágenes. Con las imágenes que
habi ualmen e se án en ada de es os algo i mos (suelen ene
disposiciones más sencillas) el algo i mo p opues o no come e
e o es.
TABLA I. ANÁLISIS DE LA BONDAD DEL ALGORITMO PROPUESTO:
VALORES MEDIOS DE ERROR
VI. IMPLEMENTACIÓN DEL ALGORITMO PROPUESTO
A. He amien as y me odología de diseño
El p oceso seguido, así como las he amien as usadas en
él, se mues an en la Fig. 6. Se ha pa ido de una
implemen ación so wa e en Ma lab ( iche o .m) que ha sido
aducida a un modelo Simulink (.mdl). Dicho modelo,
compues o po bloques an o de la lib e ía básica de Simulink
como del Xilinx Blockse , ha sido e i icado a ni el lógico y
uncional desde Ma lab, as lo cual se ha compilado,
gene ándose en el p oceso los iche os de un p oyec o ISE.
Desde el en o no ISE, se han ealizado es imaciones de á ea y
iempo y o as ope aciones de es . Po úl imo, pa a comp oba
que el uncionamien o eal del sis ema es el deseado, se ha
lle ado a cabo una co-simulación HW/SW, ce ando el lazo en
el lujo de diseño.
B. Implemen ación
Se han ealizado dos implemen aciones sob e FPGA del
algo i mo p opues o, conside ando, en ambos casos, la
conec i idad en un en o no de 4 ecinos. Una de ellas pe mi e
educi el núme o de ecu sos usados en el disposi i o a cos a
de la u ilización de dos ciclos en el p ocesamien o de cada
píxel en cada ase, mien as que la o a minimiza el núme o de
ciclos in e ido en p ocesa cada píxel haciendo uso de una
can idad mayo de memo ia.
En ambos diseños, la implemen ación de la ase inicial del
mé odo emplea como bu e una memo ia de dos pue os que
pe mi e almacena las e ique as empo ales asignadas a los
píxeles de dos ilas consecu i as. De es a o ma, en el
e ique ado de cada píxel, se dispone de las e ique as de los
píxeles de la másca a si uados en la ila an e io (en la Fig. 2
(b) los píxeles p, q y en el e ique ado de x), las cuales ue on
almacenadas con an e io idad, y de espacio su icien e pa a
gua da la e ique a que acaba de se asignada (cada una de
es as dos ope aciones, el acceso a pa a ob ene el equi alen e
al pixel q en cada ciclo y la esc i u a de x, se lle an a cabo po
un pue o di e en e de la memo ia). Las e ique as de los
pixeles del en o no del píxel x son a su ez en ada de
di ección de una memo ia o abla de equi alencias que
p opo ciona, en cada ins an e, los alo es con los cuales se
calcula el mínimo que a a se almacenado. Además, pa a
cada píxel se á necesa io comp oba si hay equi alencia en e
las e ique as ecinas. Si la hay, es a es almacenada po un
segundo pue o de la memo ia de equi alencias.
El hecho de que los diseños a en de op imiza el á ea
ocupada sus i uyendo una memo ia de e ique as empo ales
po es e bu e conlle a, además, que sea necesa ia la lec u a
de la imagen en dos ocasiones, así como la inicialización de
es e bu e de e ique as en e la ase inicial y la ase de
sus i ución pa a que no exis an e o es en el e ique ado al
eu iliza los bloques ha dwa e (la ase de sus i ución se
ealiza á de la misma o ma que la ase inicial, con la sal edad
de que no se modi ica á la abla de equi alencias, y los
bloques usados en una ase es a án disponibles en la o a).
La implemen ación de la ase de esolución es di e en e en
los dos diseños. En el que in ie e dos ciclos en p ocesa cada
en ada de la abla, po un pue o se accede siemp e en lec u a
al equi alen e de una e ique a, o lo que es lo mismo, al alo
N(p)
Imágenes
Algo i mo 1
Algo i mo
p opues o
E o A
E o R
E o A
E o R
4
Tex u as
119,22
8,89
13,88
1,07
Aé eas
76,11
3.46
11,55
0,5
Misceláneas
19,33
2.83
3,6
0,3
Miscelaneas con un
p ep ocesamien o de
de ección de bo des
0,9
7,4
0
0
8
Tex u as
85,22
13,84
1,55
0,18
Aé eas
88
7,99
1,88
0,14
Misceláneas
25,8
6.34
0,73
0,2
Miscelaneas con un
p ep ocesamien o de
de ección de bo des
6,74
47,83
0
0
Figu a 5. Ejemplo de las ope aciones de p ep ocesamien o
ealizadas a las imágenes usadas como en ada
Figu a 6. He amien as usadas en el lujo de diseño

de esa en ada de la abla. Po el o o pue o, en un ciclo se
accede en esc i u a pa a almacena el nue o alo de la
en ada an e io a la que es á siendo conside ada, mien as que
en el o o se accede en lec u a pa a ob ene el equi alen e del
equi alen e ob enido del p ime pue o. En el diseño que
in ie e an solo un ciclo en p ocesa cada píxel son necesa ias
dos memo ias de equi alencias iguales pa a pode accede , en
un mismo ciclo, al equi alen e de una e ique a (T(Labeli)) y al
equi alen e del equi alen e de la e ique a an e io (T(T(Labeli-
1)), el cual se á almacenado po el o o pue o de las memo ias
en la en ada co espondien e a la Labeli-1.
Pues o que las memo ias son ecu sos compa idos po las
dis in as ases del p ocedimien o, es necesa io accede a ellas
median e bancos de mul iplexo es con olados median e
señales de ase.
C. Resul ados de la implemen ación
T as sin e iza los diseños pa a una placa SPARTAN 3A
DSP (XC3SD1800A), se comp ueba que la mayo imagen que
es posible sin e iza sin el uso de memo ia ex e na
conside ando una abla de equi alencias máxima es de
330x240 en el caso del diseño de un ciclo y de 400x370 en el
caso del diseño de dos ciclos. No obs an e, en la mayo ía de
los casos, el núme o de e ique as asignadas en la p ime a
pasada no excede del 20% de las que se pueden asigna . Si se
conside ase una abla de equi alencias con el 30% del amaño
máximo, se ía posible sin e iza imágenes con esoluciones de
has a 500x460 y 670x600 espec i amen e. En ambos casos, el
ecu so que limi a el amaño máximo de imagen con el cual es
posible abaja son los bloques de memo ia RAM de doble
pue o de 16 kb de da os, ya que los po cen ajes de u ilización
del es o de ecu sos son muy bajos (ej. sólo se usan un 3% de
los ''Slice Flip Flops'' y ''4 inpu s LUTs'' disponibles en la
placa). La ecuencia máxima de eloj ob enida es
ap oximadamen e de 32 MHz. Con es os da os, se es ima que
con el p ime diseño se puede abaja en iempo eal con el
amaño de imagen máximo sin e izable (es deci , si nos
ajus amos a los es ánda es de ídeo exis en es, es posible
abaja con un es ánda WCIF) siendo la RAM disponible el
ecu so que impide abaja con dimensiones mayo es. El
segundo diseño, po el con a io, es á limi ado po la elocidad
a la cual es posible abaja . Con él, se puede abaja en
iempo eal con esoluciones de has a 640x480 (VGA).
VII. CONCLUSIONES
Como consecuencia de los eque imien os de las nue as
pla a o mas u ilizadas po los sis emas de isión, es necesa io
lle a a cabo un p oceso de ediseño de los algo i mos de
a amien o de imágenes que han enido implemen ándose
median e so wa e en p ocesado es de p opósi o gene al. En
es e a ículo se p opone un nue o algo i mo CCL que, al habe
sido diseñado eniendo en cuen a su implemen ación
ha dwa e, cons i uye una buena opción pa a in eg aciones en
disposi i os empo ados, alcanzándose con él un comp omiso
adecuado en consumo de ecu sos, elocidad de ope ación y
calidad en el e ique ado. Además, en su diseño se ha seguido
una me odología no edosa, que ha pe mi ido aco a los
iempos de desa ollo y acili a la ealización de p uebas de
in eg ación del algo i mo en sis emas complejos.
BIBLIOGRAFÍA
[1] F.Chang, C. Chen,”A componen -labeling algo i hm using con ou
acing echnique", P oc. In . Con . Documen Anal. Recog., págs. 741–
745, 2003
[2] D.G. Bailey, C.T.Johns on, "Single Pass Connec ed Componen s
Analysis", P oceedings o Image and Vision Compu ing, New Zeland,
págs. 282-287, 2007.
[3] Ha alick, R.M. "Some neighbo hood ope a ions". [au . lib o] M Onoe,
K. J . P es on y A Rosen eld. "Real Time Pa allel Compu e Image
Analysis". New Yo k : Plenum P ess, págs. 11-35, 1981.
[4] K.Suzuki, I.Ho iba, N.Sugie, "Fas connec ed-componen labeling
based on sequen ial local ope a a ions in he cou se o o wa d as e
scan ollowed by backwa d as e scan", P oc. o 15 h In e na ional
Con e ence on Pa e n Recogni ion, Ba celona, Spain, págs. 434-437,
Sep 3-7 2000.
[5] K.Suzuki, I.Ho iba, N.Sugie, "Linea - ime connec ed-componen
labeling based on sequen ial local ope a ions". Compu e Vision and
Image Unde s anding 89, págs. 1-23, 2003.
[6] A.Rosen eld, J.L Plaz , "Sequen ial ope a o in digi al pic u es
p ocessing", Jou nal o ACM, ol 13,4, págs. 471-494,1966.
[7] R.Lumia, L.Shapi o, O.Zungia, "A new connec ed componen s
algo i hm o i ual memo y compu e s", Compu . Vision, G aphics,
and Image P ocess. 22 (2), págs. 287–300, 1983.
[8] L.He, Y.Chao, l.Suzuki, "A un-based wo-scan labeling algo i hm",
IEEE T ans. Image P ocess., ol. 17, no. 5,, págs. 749–756, 2008.
[9] K.Wu, E.O oo, A. Shoshani , "Op imizing connec ed componen
labeling algo i hms", P oc. SPIE Con . Med. Imag, ol 5747, págs.
1965–1976, 2005.
[10] K.Wu, E.O oo, K.Suzuki, "Op imizing wo-pass connec ed-componen
labeling algo i hms", Pa e n. Anal. Applic. 12, págs. 117-135, 2009.
[11] R.Mille , Q.F. S ou , "Va ying diame e and p oblem size on mesh-
connec ed compu e ", P oc. In l. Con . Pa . P oc, págs. 679-699, 1985.
[12] D. Nassini, S.Sahni, "Finding connec ed componen s and connec ed
ones on a mesh-connec ed pa allel compu e " SIAM J.Compu , ol. 9,
no 4, , págs. 744-757, 1980
[13] A. Ag awal, L. Nekludo a, W.Lim, "A pa allel O(log(N)) algo i hm
o inding connec ed componen s in plana images",
P oc.In .Con .Pa allel P ocessing, págs. 783-786, 1987.
[14] R.Cyphe , J.L.C Sanz, L. Snyde "Algo i hms o image componen
labeling on SIMD mesh connec ed compu e s", IEEE T ans. Compu ,
ol.39, no.2, págs. 276-281, 1990.
[15] H.M. Alnuwei i, V.K. P asanna, "Fas image labeling using local
ope a o s on mesh-connec ed compu e s" IEEE T ans. Pa .Anal.
Machine In ell, ol 13, no 2, págs. 202-207, 1991.
[16] H. Shi, G.X. Ri e , "O(n)-Time and O(logn)-Space Image Componen
Labeling wi h Local Ope a o s on SIMD Mesh Conec ed Compu e s",
In e na ional Con e ence on Pa allel P ocessing, págs. 98-101, 1993.
[17] S.-W Yang e al.,"Vlsi a chi ec u e design o a as pa allel label
assignmen in bina y image", Ci cui s and Sys ems, ISCAS 2005. IEEE
In e na ional Symposium, ol 3, págs. 2393–2396, 2005.
[18] H. Fla e al., "A Pa allel Ha dwa e A chi ec u e o Connec ed
Componen Labeling Based on Fas Label Me ging". Applica ion-
Speci ic Sys ems, A chi ec u es and P ocesso s, 2008. In e na ional
Con e ence, págs. 144 - 149, 2008.
[19] S.-W Yang e al ,"Pa allel 3-Pixel Labeling Me hod and i s Ha dwa e
A chi ec u e Design", Fi h In e na ional Con e ence on In o ma ion
Assu ance and Secu i y, 2009.
[20] D.K. Kim e al. "Real-Time Componen Labeling and Bounda y
T acing Sys em Based on FPGA". In e na ional Con e ence o Robo ics
and Biomime ics, P oceedings o he 2007 IEEE, Sanya, China, págs.
15-18, 2007.
[21] USC-SIPI(Uni e si y o Sou he n Cali o nia- Signal and Image
P ocessing Ins i u e. [En línea] h p://sipi.usc.edu/da abase/.
[22] Be keley Compu e Vision (Uni e si y o Cali o nia). [En línea]
h p://www.eecs.be keley.edu/Resea ch/P ojec s/CS/ ision/g ouping/ e
sou ces.h ml.