Localización y decodificación de códigos de barras en imágenes digitales

Ingenierıa InformaticaProyectos Informaticos (E80)

Localizacion y decodificacion de codigos de barras

en imagenes digitales

Proyecto presentado por:

Vicente Castello Martınez

y dirigido por:

Vicente Javier Traver Roig

Castellon de la Plana, Julio de 2005

Resumen

Esta memoria describe un metodo para la localizacion y posterior decodificacion de codigos debarras presentes en imagenes digitales. El codigo de barras puede aparecer en cualquier posiciony orientacion dentro de la imagen, con lo cual debemos ser capaces de detectarlo y rectificar suorientacion, para ası poder decodificarlo de forma correcta.

Una tecnica que se presenta, debido a que los codigos de barras poseen unas caracterısticasmuy definidas, como un metodo adecuado para la localizacion de un codigo de barras dentrode una imagen es la deteccion de bordes. Ademas, como los puntos de borde pertenecientes alcodigo presentaran una orientacion similar, el objetivo sera de alguna forma homogeneizar estazona donde se encuentra el codigo, extendiendo el valor de la orientacion obtenido de los puntosde borde a los que no lo son. A continuacion, debido a este proceso de expansion de la orientacionconseguiremos un conjunto de regiones candidatas, de las cuales debemos ser capaces de poderelegir una de ellas como susceptible de contener el codigo. A partir de esta region debemoscalcular la orientacion que presentan los puntos de borde de la misma, para poder rectificarası la imagen. Una vez conseguida una subimagen centrada en el codigo intentamos decodificareste con exito, basandonos en lo que conocemos del tipo de codificacion en concreto.

Por ultimo comentar que durante toda la memoria se presentan los resultados que se vanconsiguiendo para cada una de las fases en las que se divide el metodo, ademas de una serie deexperimentos para reforzar la comprension del mismo o recalcar ciertos aspectos que se creen deinteres.

iii

Agradecimientos

En unas pocas palabras quisiera agradecer a una serie de personas la ayuda que me han presta-do en la realizacion de este proyecto. Estas son Ma Angeles Lopez (por su implementacion deldetector de bordes de Canny), Raul Montoliu (por su codigo para el etiquetado de componentesconexas) y Vıctor Jimenez (por sus ideas acerca de posibles estrategias a seguir para la decodi-ficacion), sin los cuales el esfuerzo realizado hubiese sido enormemente mayor. Por ultimo y nopor ello menos importante, agradecer en gran medida a mi director, Javier Traver, el tiempoque me ha dedicado y la paciencia que ha tenido conmigo, ya que sin su colaboracion no hubiesepodido afrontar este proyecto. Simplemente, muchas gracias.

v

Indice general

1. Introduccion 1

1.1. Motivacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Organizacion de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3. Trabajos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2. Codigos de barras 7

2.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2. Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3. Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4. Ventajas e inconvenientes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5. Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.6. Clases de codigos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.7. Dispositivos de escritura y lectura de codigos de barras . . . . . . . . . . . . . . . 11

3. Deteccion de bordes 15

3.1. Tecnicas de localizacion de codigos de barras . . . . . . . . . . . . . . . . . . . . 153.2. Detector de bordes de Canny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.3. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4. Deteccion de regiones candidatas 19

4.1. Idea general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.2. Procedimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.3. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5. Etiquetado y filtrado de regiones 23

5.1. Etiquetado de componentes conexas . . . . . . . . . . . . . . . . . . . . . . . . . 235.2. Procedimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235.3. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

6. Estimacion de la orientacion y rectificacion 31

6.1. Idea general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316.2. Procedimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

7. Decodificacion 33

7.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337.2. Procedimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347.3. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377.4. Analisis de robustez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

vii

Indice general

8. Sistema experimental 458.1. Informacion general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458.2. Restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468.3. Valores por defecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468.4. Tiempo de ejecucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478.5. Duracion del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

9. Conclusiones 49

A. Detector de bordes de Canny 51

B. Algoritmo clasico de etiquetado de componentes conexas 53

C. Metodo de Otsu 55

D. Caracterısticas del codigo EAN-13 57

viii

1. Introduccion

1.1. Motivacion

Hoy en dıa los codigos de barras estan muy presentes en nuestro quehacer diario, ya quenos aparecen en los supermercados, tiendas de toda clase, en los libros de las bibliotecas, etc.,debido a que permiten obtener una especificacion unica de un producto o material en concreto.Sin embargo no debemos olvidar que los codigos de barras necesitan de instrumentos que puedanleerlos, al igual que de un software que permita captar y procesar la informacion.

Ademas en entornos controlados, las camaras pueden ser usadas para la identificacion deobjetos, es decir, si los objetos de nuestro interes presentan etiquetas de codigos de barras enuna superficie visible, entonces un simple sistema de camaras portatiles puede reconocer el codigode barras en el entorno y proporcionar al usuario informacion sobre el objeto etiquetado [26].

Por todo ello este proyecto intenta ofrecer un metodo de localizacion de un codigo de barrasdentro de una imagen, para su posterior decodificacion. Se ha utilizado una serie de procedimien-tos que nos han permitido conseguir nuestro objetivo y que se explican con detalle posteriorescapıtulos de esta memoria.

Como es obvio, hay una gran variedad de codigos de barras, pero en este proyecto nos hemoscentrado en una clase en concreto, el codigo EAN (European Article Number) y mas concreta-mente en su version EAN-13 [20], que aunque dicho de esta forma no nos suene mucho, es uno delos codigos mas presentes en nuestras vidas, ya que se utiliza en una gran cantidad de productosde todo tipo, desde cualquiera de los artıculos presentes en un supermercado hasta toda clasede libros. Es en este ultimo uso donde nos centraremos, ya que los libros se codifican basandoseen un sistema internacional de numeracion, el ISBN (International Standard Book Number) [9],el cual utiliza para su codificacion el codigo EAN-13.

Si sabemos que los dıgitos que encontramos normalmente impresos junto a las barras y espaciosde un codigo de barras suelen ser aquellos codificados dentro de este, por que no leer estos dıgitosen lugar de decodificar estas barras y espacios. La razon principal es que, incluso con los modernossistemas de reconocimiento optico de caracteres (OCR, Optical Character Recognition), no esposible identificar las cifras de un codigo numerico con la suficiente rapidez, facilidad y fiabilidadque se requiere y por tanto no queda otra solucion mas que representar el codigo mediantesımbolos facilmente legibles por el ordenador, empleando sus sistemas binarios.

Otra pregunta que puede surgir es por que investigar en este tema si los sistemas existentesya funcionan correctamente. Una de las razones es la posibilidad de que cualquier persona conuna camara, como por ejemplo una simple webcam, pudiese decodificar codigos de barras en supropia casa si lo precisase, ya que es mas facil que un particular pueda adquirir una camara deeste tipo que un lector laser por ejemplo, mucho mas caro. Incluso podrıa ser utilizado por elpequeno y mediano comercio, resultando una opcion mucha mas economica.

1.2. Organizacion de la memoria

La memoria esta dividida en una serie de capıtulos donde cada uno de ellos presenta lasiguiente informacion:

1

1. Introduccion

El capıtulo 2, ((Codigos de barras)), se dedica a aportar una serie de datos relacionados conlos codigos de barras: definicion, ventajas e inconvenientes, aplicaciones, lectores, etc., amodo de informacion introductoria al mundo de los codigos de barras.

En el capıtulo 3, ((Deteccion de bordes)), se explica la idea fundamental que se sigue parala localizacion del codigo de barras y es que debido a las caracterısticas que este posee,la deteccion de bordes se presenta como una tecnica mas que adecuada para su posibledeteccion.

En el capıtulo 4, ((Deteccion de regiones candidatas)), nos centramos en la idea que a la horade detectar el codigo de barras los pixels que son puntos de borde y forman parte del codigovan a tener una orientacion similar. Con esta caracterıstica lo que se pretende es expandiresta orientacion a los vecinos de cada uno de los puntos de borde y ası, homogeneizar todala zona donde se encuentra el codigo con una misma orientacion.

En el capıtulo 5, ((Etiquetado y filtrado de regiones)), explicamos como tras el paso anteriormediante un proceso de agrupamiento, extendiendo la orientacion y gracias a una posteriorbinarizacion, conseguimos obtener una serie de regiones susceptibles de ser la que se busca.Utilizando algoritmos de etiquetado de componentes conexas y realizando a continuacionun filtrado, podemos quedarnos con la region que ((supuestamente)) contiene el codigo.

En el capıtulo 6, ((Estimacion de la orientacion y rectificacion)), se indica como, al poderpresentar el codigo cualquier angulo dentro de la imagen, se debe calcular la orientacionque presentan los puntos de borde que aparecen en esta region susceptible de conteneral codigo y que hemos obtenido en el paso anterior. Una vez conocida esta orientacionsimplemente debemos rectificar la imagen y conseguir una imagen centrada en el codigo,para su posterior binarizacion.

En el capıtulo 7, ((Decodificacion)), se explica como basandonos en la imagen binarizada delcodigo de barras obtenida en el paso anterior, y empleando el conocimiento que tenemosdel tipo de codigo a interpretar (EAN-13 ), se obtiene la consiguiente decodificacion delmismo.

El capıtulo 8, llamado ((Sistema experimental)), presenta informacion relativa al proyectoy que creemos que debe ser mencionada, desde el software utilizado para la realizacion delproyecto hasta el tiempo en que tarda en ejecutarse la tecnica implementada.

En el ultimo capıtulo simplemente mencionamos las conclusiones a las que llegamos despuesde la realizacion de este proyecto.

De forma grafica el proceso que se ha seguido para la localizacion y posterior decodificacionde un codigo de barras se puede observar en la Figura 1.1. Cada una de las fases que componenel proceso en general se explican con mas detalle, y como hemos comentado anteriormente, enlos correspondientes capıtulos que aparecen en esta memoria.

1.3. Trabajos relacionados

Previamente y durante la realizacion de este proyecto se ha ido recopilando informacion deartıculos y trabajos relacionados con codigos de barras, algunos de los cuales vamos a comentaren este punto, ya que han servido de complemento y ayuda al igual que nos han ofrecido ideaspara la realizacion del metodo, o simplemente pueden resultar de interes para conocer con mayordetalle el estado del arte o profundizar en el tema.

2


La decodificacion de codigos de barras danados es un tema que se presta a estudio. Un ejemploserıa la decodificacion de los codigos de barras que nos aparecen en las recetas medicas y que seven afectados por firmas o cualquier otro tipo de mancha [22]. El metodo en cuestion se basaen la utilizacion de la transformada de Hough como herramienta que permite la busqueda delıneas verticales dentro de una imagen. La tecnica implementada consigue leer alrededor de un85 % de las prescripciones que se analizan, sin embargo cabe destacar que el proceso asume que,a diferencia de nuestro proyecto, el codigo ya se encuentra en una orientacion mas o menosadecuada para ser procesado por el algoritmo.

Sin embargo los estudios realizados no solo se han centrado en la localizacion de las barrasy los espacios que conforman el codigo, sino que han llegado a plantearse otra opcion como, eldecodificar un codigo de barras a partir de los dıgitos presentes junto a las barras del mismo [5].Los sistemas de analisis de imagen normalmente requieren que la imagen donde se encuentra elcodigo de barras a analizar tenga una resolucion lo suficientemente buena para su decodificacion.Gracias a este nuevo metodo se consigue que la imagen pueda presentar una baja resolucion yse decodifique el codigo con exito, ya que los caracteres o dıgitos presentes debajo del codigode barras pueden verse menos afectados por un emborronamiento o una baja resolucion dela imagen, con lo cual pueden convertirse en una acertada fuente de informacion, mejor queel patron de barras. En este metodo la localizacion del codigo de barras se realiza a partirdel analisis del gradiente. Una vez localizado el codigo, basandose en el tipo de codificacionque se quiere decodificar, se determina donde se encuentra la zona que incluye los caracteresque representan al codigo, para posteriormente mediante tecnicas de probabilidad y estadısticadeterminar a que dıgitos corresponden.

Dentro del campo de la robotica tambien resulta de interes la localizacion y posterior de-codificacion de codigos de barras. Se ha llegado a investigar en temas como el desarrollo de unsistema robotizado que, utilizando algoritmos de procesamiento de imagenes, intenta reconocery decodificar los codigos de barras que aparecen en una gran variedad de barriles utilizadosen algunos sectores industriales para almacenar toda clase de residuos. Al mismo tiempo estereconocimiento sirve para realizar una especie de inventario de los barriles inspeccionados [31].El procedimiento se basa en dos fases: una primera en la que la imagen es procesada aplicandofiltros adaptativos de umbralizacion del gradiente. Este filtrado identifica bordes verticales en laimagen. En la segunda fase la imagen es analizada por areas que tienen una alta concentracionde estos bordes verticales, asumiendo que son zonas con una alta probabilidad de ser el codigode barras, idea parecida a la que se utiliza en nuestro metodo donde se consiguen regiones deorientacion similar susceptibles de contener el codigo. Sin embargo presenta inconvenientes co-mo la aparicion de falsos positivos, debido a que la imagen puede presentar zonas con bordessimilares a los de un codigo de barras y por tanto detectarse como zona donde se encuentra elcodigo cuando no lo es. Ademas tambien se ve bastante influenciado por el tamano del codigode barras respecto a la imagen.

Normalmente los sistemas de analisis de imagenes requieren que el codigo de barras este con-tenido completamente en la imagen, sin embargo se han realizado investigaciones para evitaresta limitacion. Un trabajo relacionado con este aspecto desarrollaba un metodo para la decod-ificacion de codigos de barras captados con una camara, cuyo campo de vision es mas pequenoque el tamano del propio codigo, con lo cual debıa capturar distintas imagenes, que una vezjuntas, reconstruıan el codigo, para posteriormente decodificarlo [28]. La localizacion del codigose realiza mediante el calculo del gradiente y buscando zonas donde la orientacion del mismo essimilar. Esta misma idea es en la que nos basamos en nuestro metodo para la localizacion delcodigo de barras. Una vez detectado el codigo se aprovecha el conocimiento que se posee del tipode codigo que se esta analizando para conseguir una correcta decodificacion. En nuestro proyectotambien explotamos este conocimiento que tenemos del codigo de barras para su decodificacion.

3

1. Introduccion

Relacionado con la problematica de la teorıa de senales podemos encontrar trabajos que tratande interpretar el codigo de barras a partir del tratamiento o reconocimiento de los picos presentesen la senal u onda obtenida del mismo [18]. Se utilizan modelos estadısticos de reconocimientopara clasificar estos picos como los caracteres presentes en el codigo. Mediante esta tecnica seconsigue mejores resultados ante codigos emborronados, ya que el proceso es mas resistente antetales contratiempos.

La ciencia no solo ha investigado en la mejora de tecnicas de decodificacion de codigos debarras en cuanto a procesamiento de imagenes, sino que tambien se ha preocupado por mejorarlas prestaciones de los escaneres lectores de codigos. Un ejemplo es una investigacion realizadacon el objetivo de ofrecer mejoras en el funcionamiento de los escaneres a traves de un muestreoselectivo y el uso de filtros de realzado para mejorar la deteccion de bordes, que detectan lasfronteras entre areas oscuras y claras (barras y espacios) [27]. Otros estudios se centran masen obtener tecnicas destinadas a la mejora de la decodificacion de codigos de barras borrosos oemborronados [30].

4


Figura 1.1.: Diagrama global del proceso implementado

5

1. Introduccion

6

2. Codigos de barras

2.1. Introduccion

Como informacion preliminar, antes de comenzar a explicar el metodo desarrollado, se hacreıdo conveniente aportar informacion general sobre los codigos de barras. Por ello, en estepunto de la memoria se presentan una serie de datos acerca de este sistema de codificacion.

Empezamos con una breve descripcion de los codigos de barras, su nomenclatura basica y unaserie de caracterısticas. A continuacion nos adentramos en su historia [2], cuando surgieron y suposterior desarrollo, ventajas e inconvenientes que presentan y un conjunto de aplicaciones en lasque los codigos de barras suelen ser de gran utilidad. Por ultimo se mencionan las distintas clasesde codigos que existen, para acabar comentando diferentes tipos de impresoras [4] y lectores paraesta clase de codificacion en concreto.

2.2. Definicion

Los codigos de barras son un sistema de codificacion creado con el objetivo de identificarobjetos y facilitar la obtencion de informacion y de esta forma eliminar la posibilidad de erroren la captura. La utilizacion de este sistema de codificacion es tan exitosa debido a la fiabilidadque presenta en la recoleccion automatica de datos, reduciendo los posibles errores humanos quese pueden producir en el caso de una introduccion erronea de informacion.

Podemos definir un codigo de barras como un patron formado por barras y espacios parale-los que codifica informacion mediante las anchuras relativas de estos elementos. Su estructurabasica consiste de un patron de inicio, uno o mas caracteres de datos, opcionalmente unos o doscaracteres de verificacion y un patron de termino.

Ademas implementar un sistema de captura de datos por codigos de barras es poco costosoy el conocimiento necesario para utilizar el sistema es mınimo, por lo que no debe presentarsecomo un problema el aprendizaje del personal que manipule el mismo.

El desarrollo de este sistema de codificacion nos permite disponer de tres categorıas de codigosde barras, dependiendo de la tecnologıa que es necesaria para realizar una lectura de los mismos:lineales, multifilas y bidimensionales. Una gran parte de la literatura existente llama tambiencodigos bidimensionales a los considerados multifilas. Por tanto se puede realizar una divisionentre codigos de una dimension (lineales) donde solo importa el ancho de las barras y el espacioentre ellas y codigos de dos dimensiones (multifilas y bidimensionales) donde importa la alturay anchura del sımbolo.

Nomenclatura basica

La visualizacion fısica de los codigos de barras suele presentarse mediante barras verticales:estas representan caracteres de informacion mediante barras negras y espacios, donde el anchode las barras y espacios puede ser variable. Por tanto, cada dıgito o caracter representado en uncodigo esta formado por barras y espacios que tienen una anchura total de una cierta cantidadde unidades o modulos, dependiendo del codigo, de esta forma cada barra y cada espacio puedetener una anchura de diversas unidades o modulos. De forma resumida se puede expresar de lasiguiente manera:

7


Modulo: es la unidad mınima o basica de un codigo. Las barras y espacios estan formadospor un conjunto de modulos.

Barra: el elemento ((oscuro)) dentro del codigo. Se hace corresponder con el valor binario 1.

Espacio: el elemento ((claro)) dentro del codigo. Se hace corresponder con el valor binario 0.

Caracter: formado por barras y espacios. Normalmente se corresponde con un caracteralfanumerico.

Todo esto se observa mejor graficamente en la Figura 2.1.

Figura 2.1.: Cada caracter o dıgito esta formado por un conjunto de modulos

Caracterısticas

Un sımbolo de codigo de barras presenta una serie de caracterısticas entre las cuales cabedestacar las siguientes:

Densidad: es la anchura del elemento, ya sea barra o espacio, mas estrecho dentro delsımbolo de codigo de barras. Un codigo de barras no se mide por su longitud fısica sinopor su densidad, que viene dada en milesimas de pulgada.

Razon ancho-estrecho (Wide to Narrow Ratio (WNR)): Es la relacion existente entre elgrosor del elemento mas estrecho con respecto al mas ancho. Normalmente es de 1:3 o 1:2.

Zona muda (Quiet Zone): Es el area blanca que aparece al principio y al final de unsımbolo de codigo de barras y que es necesaria para una acertada lectura del sımbolo.

2.3. Historia

El codigo de barras como sistema de codificacion tiene aceptacion mundial y hoy en dıa es unrequisito indispensable para que los productos de una determinada empresa puedan ser comer-cializados tanto en el mercado interior como en el exterior. Pero mucho antes de que los codigosde barras aparecieran, ya surgıan investigaciones relacionadas con sistemas de codificacion deinformacion.

En 1932, Wallace Flint, un estudiante de la Universidad de Harvard, realizo un proyectofinal de carrera (master thesis) que desarrollaba un sistema mediante el cual los clientes de unsupermercado podrıan marcar aquello que quisieran comprar en una serie de tarjetas perforadas,

8

2.3. Historia

que posteriormente se introducirıan en una serie de lectores que activarıan un sistema automaticoque les proporcionarıa aquello demandado.

Sin embargo la idea de codigo de barras conforme lo entendemos hoy en dıa nacio en 1948. Enese ano Bernard Silver, un estudiante graduado del Instituto Drexel de Tecnologıa de Filadelfia,escucho por casualidad como el presidente de una cadena de supermercados le pedıa a uno de losdecanos que emprendiese una investigacion para desarrollar un sistema que permitiese la lecturaautomatica de informacion de los productos durante el cobro de los mismos.

Silver conto lo que habıa escuchado a su amigo Normand Joseph Woodland, que ejercıa comoprofesor en esa misma universidad. La idea le fascino y empezaron a investigar en el tema.Despues de un ano de gran esfuerzo Woodland y Silver registraron en 1949 la primera patentepara un codigo de barras. El sistema que tenıa forma circular se denomino ((bull’s eye code)) yconsistıa en una serie de cırculos concentricos con el objetivo de que pudiera leerse en cualquierdireccion.

Tres anos mas tarde, en 1952, construyeron el primer lector de codigos de barras, perolamentablemente el sistema no consiguio ser demasiado efectivo, al igual que resultaba caro,por lo que no llego a comercializarse.

Los codigos de barras se emplearon por primera vez a principios de la decada de los 60 paraidentificar material rodante ferroviario y de ahı en adelante ha venido avanzando su aplicaciony desarrollo. A finales de los anos 60 y comienzos de los 70 aparecieron las primeras aplicacionesindustriales, pero solo para manejo de informacion.

Durante esos anos la Asociacion Nacional de Cadenas Alimenticias (NAFC, de las siglas eningles) se dio cuenta que debıan solucionar de una vez por todas los problemas que se presentabana la hora del cobro de sus productos. Por ello, en 1967, la cadena de supermercados Kroger instalael primer sistema de venta basado en codigos de barras en su sucursal de Cincinnati (Ohio, EE.UU.). El experimento presento una serie de problemas que sirvieron para la mejora del sistemay de esta forma su posterior adaptacion a todos los productores y comerciantes del sector.

Durante los anos 70 y primeros de los 80 se produjo la evolucion de los codigos lineales. Suutilizacion se difunde a varios sectores utilizandose en muy distintas tareas, desde el control dedocumentos en bibliotecas, hasta la identificacion y verificacion automatica en los bancos desangre.

En el ano 1973 se anuncia la aparicion del codigo UPC (Universal Product Code) que seconvertirıa en el estandar de identificacion de productos en los Estados Unidos. Como anecdota,comentar que el primer producto escaneado en un punto de pago utilizando este codigo fue unpaquete de chicles, el cual se encuentra hoy en dıa expuesto en el Museo Nacional de HistoriaAmericana. En 1976, Europa desarrolla su propia version de UPC, el codigo EAN (EuropeanArticle Number), del cual se desarrollarıan dos versiones: el EAN-13 y el EAN-8.

En 1974, se inventa el codigo 39, el primero de tipo alfanumerico y trece anos mas tarde, en1987, se desarrolla el primer codigo bidimensional, el codigo 49, primer codigo multifilas queaparecio en el mercado.

Poco a poco, durante los anos 80 y 90, la tecnologıa de identificacion y manejo de datos atraves de codigos de barras, logra convertirse en un estandar al ser aplicada, cada vez con masfrecuencia, tanto en operaciones de distribucion y manejo de materiales, como en organizacionesde manufactura industrial, al igual que en todo tipo de nuevos ambitos. Durante los anos 90fueron apareciendo nuevos tipos de codigos y se desarrollaron sobretodo los codigos de altadensidad o bidimensionales.

9


2.4. Ventajas e inconvenientes

La tecnologıa de codigo de barras presenta una serie de ventajas sobre otros procedimientosde coleccion de datos, estas son:

Se imprime con costes bajos.

Su precision en la informacion, evitando o reduciendo de esta forma los errores.

Su eficiencia debido a la rapidez en la lectura, ahorrando tiempo y dinero.

La relativa flexibilidad y facilidad de conexion e instalacion de los equipos de lectura eimpresion de codigo de barras.

Por contrapartida, no todo son ventajas, tambien presentan inconvenientes, como los que acontinuacion mencionamos:

En general los codigos de barra no son facilmente descifrables por las personas, necesitandopues lectores que nos decodifiquen la informacion.

La facilidad con la cual es posible dificultar la legibilidad de ciertos codigos, es decir,simplemente con agregar una barra al inicio o final del sımbolo o trazar una lınea paralela alas barras en cualquier lugar dentro del codigo, complica en gran manera su decodificacion.

2.5. Aplicaciones

Las aplicaciones del codigo de barras cubren practicamente cualquier tipo de actividad hu-mana, lo podemos encontrar tanto en la industria, en el comercio, en instituciones guberna-mentales, y en un sinfin de areas, ya que cualquier sector puede beneficiarse del uso de estesistema de codificacion. Ademas, la tecnologıa que conlleva ofrece una de las mejores manerasde automatizar el manejo de informacion, ofreciendo un sistema de coleccion de datos medianteidentificacion automatica bastante rapido y seguro.

Cualquier sector donde se necesita un sistema para capturar informacion y ası mejorar laproductividad, puede optar por utilizar codigos de barras. Algunas de las aplicaciones en lasque el uso del codigo de barras se muestra como una eleccion acertada son: control de materialen proceso, control de inventario, contro de tiempo y asistencia, puntos de venta, control decalidad, bibliotecas, bancos de sangre, control de acceso, identificacion de carga, etc. Pero estasson solo una parte de la gran variedad de aplicaciones en las que se pueden utilizar codigos debarras como procedimiento de codificacion de datos.

En todas estas actividades el codigo de barras se presenta como una de las mejores tecnologıaspara implementar un sistema de captacion de datos mediante identificacion automatica, presen-tando una serie de beneficios desde la mejora de la calidad y servicio al cliente hasta una mayorcompetitividad.

2.6. Clases de codigos

La simbologıa de un codigo de barras nos define los detalles tecnicos de cada tipo particularde codigo de barras, la anchura de las barras, la forma en que se codifica la informacion en lasbarras y espacios del sımbolo de codigo de barras, etc.

Como hemos comentado anteriormente podemos distinguir entre codigos de una dimension ycodigos de dos dimensiones. En los primeros, al efectuar la lectura, se tiene en cuenta el ancho

10

2.7. Dispositivos de escritura y lectura de codigos de barras

de las barras y los espacios entre ellas, en cambio la altura de las barras no otorga ningun dato.En cierta forma estos codigos representan la clave para acceder a un registro de alguna base dedatos en donde realmente reside la informacion, o sea, los sımbolos no contienen informacion delproducto o artıculo, sino una clave unica que lo identifica.

Por tanto la pequena capacidad de codificacion de estos codigos los hace depender de sistemasde datos externos, sin el sistema externo el codigo no tiene significado. La dependencia desistemas externos de datos ofrece dos importantes ventajas:

Proporciona la posibilidad de acceder a gran cantidad de informacion utilizando un codigoy sımbolo relativamente corto.

Permite cambiar los datos asociados a este sin tener que editar o modificar nuevamente elcodigo.

El otro tipo de codificacion que surgio no hace tantos anos es la codificacion bidimensional,dentro de la cual tenemos los llamados codigos de barras apilados o multifilas (((stacked ))) y loscodigos matriz (((matrix ))). La principal ventaja de utilizar codigos de dos dimensiones es quelos datos estan codificados tanto en la altura como en la longitud del sımbolo y la informacionno se reduce solo al codigo del artıculo, sino que puede almacenar gran cantidad informacionque puede ser leıda de manera rapida y fiable, sin necesidad de acceder a una base de datos endonde se almacene dicha informacion, como ocurre en el caso de los codigos de una dimension.Por el contrario, al contener mucha mas informacion que los codigos unidimensionales requierende un escaner especial cuyo coste es mas elevado.

La seguridad que son capaces de incorporar estos codigos los hace casi invulnerables a los posi-bles agentes externos que pueden causar su deterioro, ya que este tipo de codigos han superadoinnumerables pruebas de resistencia con el objetivo de determinar su integridad.

Los codigos bidimensionales deben ser considerados como un complemento a la tecnologıatradicional de codigos unidimensionales, no como su reemplazo y las ventajas deben ser com-paradas frente al incremento en coste. Por tanto, dependiendo del tipo de necesidades de iden-tificacion interna del negocio o a los requisitos que se deben cumplir para comerciar segun lasnormas del mercado, se debe optar por un sistema de codificacion u otro.

Normalmente cuando la gente piensa en codigos de barras los suele relacionar con la tıpicasimbologıa de barras y espacios, por ello en la Figura 2.2 se muestran un par de codigos bidi-mensionales como curiosidad, ya que estos suelen ser, dentro de los codigos de barras, los masdesconocidos.

(a) (b)

Figura 2.2.: Codigos bidimensionales: (a) Codablock; (b) MaxiCode


Para poder imprimir los codigos de barras se nos presentan en el mercado distintos tipos deimpresoras que pueden llevar a cabo tal funcion. El empleo de una u otra dependera de lo que

11


el usuario requiera para cada caso en particular.Los codigos de barras se pueden imprimir en impresoras laser o de chorro de tinta con las cuales

se puede conseguir codigos de barras de alta densidad y calidad, pero, por el contrario, tambienpresentan problemas al imprimir en cantidad, al igual que las etiquetas donde se imprimen loscodigos deben tener un adhesivo especial que tolere las altas temperaturas generadas por laimpresora. Ademas, la imagen en el codigo de barras se puede danar facilmente, a menos que seutilicen recubrimientos especiales en las etiquetas o bien laminarlas una vez que se ha impresoel codigo.

Otra posibilidad es la impresion termica directa, metodo mas rapido y simple de gran aceptacionen la industria y el comercio. El coste de las etiquetas termicas es mayor comparado con el delas utilizadas para impresoras laser, pero sin embargo el coste del proceso global es menor. Portanto este tipo de impresion presenta una serie de ventajas como son su velocidad y calidad deimpresion, donde la imagen es duradera, al igual que es excelente para el trabajo por lotes. Porel contrario tambien tiene inconvenientes como que requiere etiquetas de material especial y deun tamano limitado y que la imagen puede deteriorarse en caso de exponerse a la luz solar o aaltas temperaturas.

Para obtener unos mejores resultados que en las anteriores impresoras es necesario usar unaimpresora especıfica para etiquetas, una impresora de transferencia termica, capaz de impri-mir, con gran velocidad y calidad, rollos de etiquetas autoadhesivas. Estos equipos suelen serlos mejores para aplicaciones de mediano y alto volumen, ya que reunen las ventajas de lasimpresoras laser y las termicas directas.

En la figura 2.3 se muestra un ejemplo de cada uno de los diferentes tipos de impresoras quehemos comentado en este apartado.

(a) (b) (c)

Figura 2.3.: Impresoras de codigos de barras: (a) laser; (b) termica directa; (c) de transferenciatermica

Para poder obtener la informacion presente en un codigo de barras necesitamos de dispositivosque decodifiquen la informacion presente en el mismo, por ello los lectores de codigos de barrasnos permiten obtener esta informacion, de forma que pueda almacenarse en una computadorapara poder ser procesada.

Existen muchas opciones de conexion de lectores de codigos de barras a una computadora,aunque existen dos tipos basicos: aquellos lectores que almacenan la informacion en memoriapara despues transferirla a una computadora y los lectores de radiofrecuencia que transmiten lainformacion a la computadora en tiempo real. En los primeros si la computadora central falla,la recoleccion de datos puede continuar, al igual que si falla una lector en particular, este puedeser reemplazado. Por su parte el segundo sistema presenta una verificacion de datos inmediata ymas sofisticada, con una interaccion con el usuario que consigue una mayor reduccion de errores.

El funcionamiento de los lectores de codigos de barras se podrıa explicar de la siguiente manera:el lector decodifica el codigo de barras a traves de la digitalizacion proveniente de una fuentede luz que cruza el codigo y mide la intensidad de la luz reflejada por los espacios blancos, ya

12


que las barras oscuras absorben la luz y los espacios la reflejan. El patron de la luz reflejada sedetecta a traves de un fotodiodo, el cual produce una senal electrica que coincide exactamentecon el patron impreso del codigo de barras. Un decodificador usa algoritmos matematicos paratraducir los impulsos electricos en un codigo binario y transmite el mensaje decodificado a unacomputadora como si la informacion hubiese sido introducida por teclado.

En cuanto a los lectores existe una gran variedad, pero podemos destacar cuatro que son losprincipales:

1. Lectores tipo pluma o lapiz (wand):

El modo de uso es simple, el operador coloca la punta del lector en la zona blanca queesta al inicio del codigo y lo desliza a traves del sımbolo a velocidad e inclinacion constantehaciendo contacto a lo ancho del codigo, enviandose una senal digital pura de las barras yespacios a una frecuencia igual a la velocidad con que se desliza el lapiz.

Con este tipo de lector obtenemos una serie de ventajas como son su bajo precio y sutamano reducido, por contra son susceptibles a caıdas debido a su forma, pueden sernecesarias varias pasadas para conseguir una lectura correcta, por lo tanto tiene un bajoFisrt Read Rate (FRR) y solo son practicos cuando se leen codigos impresos de gran calidadcolocados preferentemente en superficies duras, planas y horizontales.

2. Lectores CCD (Charge Coupled Device):

Son lectores de contacto que emplean un fotodetector CCD formado por una fila de LEDsque emite multiples fuentes de luz y forma un dispositivo similar al encontrado en lascamaras de vıdeo, es decir, mediante un arreglo de foto diodos toma una ((foto)) del sımbolode codigo de barras y la traduce a una senal, que puede ser similar a la enviada por el lasero a la del lapiz optico. Se requiere hacer contacto fısico con el codigo, pero a diferencia delanterior no hay movimiento que degrade la imagen al escanearla.

Algunas de las ventajas que presenta son su rapidez de lectura, es bastante duradero porno tener partes moviles, tiene un alto First Read Rate (FRR) y es economico. Sin embargono todo son ventajas ya que requiere estar muy cerca del codigo (0–1.5 cm) y no puedeleer sımbolos que rebasen el ancho de su ventana.

3. Lectores laser tipo pistola:

Realiza un barrido mediante una luz laser que genera una senal similar a la del lapizoptico, pero a una mayor frecuencia. Esta senal es conocida como HHLC (Hand HeldLaser Compatible). Un espejo rotatorio u oscilatorio dentro del equipo mueve el haz deun lado a otro a traves del codigo de barras, de modo que no se requiere movimiento porparte del operador, este solo debe apuntar y disparar. Ademas usan un mecanismo paraprevenir la lectura accidental de otros codigos dentro de su distancia de trabajo.

Presenta las siguientes ventajas: rapido, tiene un alto First Read Rate (FRR), puede leercodigos estropeados o mal impresos y puede leer a distancia, desde unos pocos centımetrosa varios metros.

Las desventajes son: puede tener problemas para leer con demasiada luz ambiental, esrelativamente caro y puede presentar problemas de durabilidad debido a sus partes moviles.

4. Lectores laser fijos omnidireccionales:

Se encuentran normalmente en las cajas registradoras de supermercados. El haz de laser sehace pasar por un conjunto de espejos que generan un patron ominidireccional, otorgandoası la posibilidad de pasar el codigo en cualquier direccion, sin importar la orientacion del

13


mismo. Los productos a leer se deben poder manipular y pasar a mano frente al lector.Son recomendables cuando se requiere una alta tasa de lectura.

Las ventajas que se obtienen con este tipo de lector son las mismas ventajas que con ellaser de pistola, ademas de presentar un First Read Rate (FRR) de practicamente el 100 %.En contrapartida es un lector caro y el operador que lo utilice requiere que los artıculosetiquetados no sean muy voluminosos pues el escaner se monta en posicion fija.

En la Figura 2.4 se muestra un lector de cada uno de los diferentes tipos que hemos mencionadoanteriormente.

(a) (b) (c) (d)

Figura 2.4.: Lectores de codigos de barras: (a) tipo pluma o lapiz; (b) lector CCD; (c) laser tipopistola; (d) laser omnidireccional

14

3. Deteccion de bordes

3.1. Tecnicas de localizacion de codigos de barras

Existen distintas tecnicas para identificar donde se encuentra un codigo de barras dentro deuna imagen [28]:

Algoritmo Morfologico Matematico: Metodo de localizacion basado en operacionesmorfologicas basicas como: dilatacion, erosion, cierre y un conjunto de operaciones mor-fologicas geodesicas. El algoritmo se basa en el hecho que los codigos de barras poseen((valles estrechos)) (espacios estrechos existentes entre las barras), un alto contraste y lıneasparalelas. Mediante una segmentacion, estos valles se juntan para formar una region quecorresponde al codigo de barras, descartando pequenas areas que no pertenecen al codigo,para a continuacion aplicar filtros morfologicos en diferentes orientaciones con el fin deextraer la orientacion del codigo de barras.

Analisis de texturas mediante filtros de Gabor: La idea fundamental sobre la quese basa este metodo es asumir que un codigo de barras es una region con una texturahomogenea. Ademas en una imagen donde se encuentra presente la textura, el nivel degris de los pixels individuales no proporcionan suficiente informacion para llevar a cabouna segmentacion satisfactoria de la imagen, por ello se hace necesario incluir las relacionesespaciales existentes entre los niveles de gris de los pixels dentro de una vecindad local.

Deteccion de texto en las imagenes: Otra idea para la localizacion de codigos de barrases utilizar tecnicas provenientes de los algoritmos de busqueda de texto, sin embargo estetipo de metodos presentan como inconveniente que suelen consumir mucho tiempo.

Densidad de Gradiente: Otro metodo de localizacion de codigos de barras es el basadoen la extraccion de areas que poseen una alta densidad de gradientes mono-orientados.La localizacion de codigos de barras en una imagen con baja resolucion es el principalproposito de este algoritmo, que utiliza para tal objetivo el calculo de gradientes y filtrosmorfologicos.

En nuestro metodo, la idea en la que nos basamos para la localizacion del codigo de barras,es muy similar a la presente en la ultima tecnica mencionada. Aunque debemos recalcar queel conocimiento sobre estas tecnicas no se produjo hasta bastante mas tarde del comienzo deeste proyecto. Simplemente, el descubrir que existıan y conocer en que se basan, sobretodo estaultima, nos llevo a pensar que no ibamos mal encaminados en cuanto a la manera en que sedetecta y localiza el codigo de barras en nuestro proyecto.

Por tanto, el objetivo final que perseguimos es conseguir la decodificacion del codigo de barras,para lo cual un paso esencial es la localizacion dentro de la imagen del codigo en cuestion.La idea fundamental que se ha seguido para conseguir esta tarea ha sido que los codigos debarras presentan unas caracterısticas que permiten su localizacion basandonos en el metodo dela deteccion de bordes, ya que cada uno de los puntos de borde que conforman el codigo debarras ((supuestamente)) presentaran una orientacion similar y por tanto, seran susceptibles deser clasificados como puntos de la imagen con una alta probabilidad de contener el codigo debarras pretendido.

15


3.2. Detector de bordes de Canny

Un concepto relacionado con la extraccion de bordes es el de la primera derivada, ya que estaes cero en todas las regiones donde no varıa la intensidad y tiene un valor constante en toda latransicion de intensidad. Por tanto un cambio de intensidad se manifiesta como un cambio bruscoen la primera derivada [24], caracterıstica esta que puede utilizarse para detectar la presenciade un borde.

Uno de los operadores basados en la primera derivada para la deteccion de bordes es elalgoritmo de Canny, que consiste en tres grandes pasos [24]:

Obtencion del gradiente (magnitud y orientacion del vector gradiente en cada pıxel).

Supresion no maxima o adelgazamiento del ancho de los bordes, obtenidos con el gra-diente, hasta lograr bordes de un pıxel de ancho.

Histeresis de umbral al resultado de la supresion no maxima, con este proceso se pre-tende reducir la posibilidad de aparicion de falsos contornos.

Por tanto, en primer lugar a la imagen se le aplica un filtro gaussiano, para suavizar la imageny tratar de conseguir la eliminacion del posible ruido que afecte a la misma. Sin embargo hayque ir con cuidado para no realizar un suavizado excesivo de la imagen y perder detalles ocaracterısticas de interes, provocando de esta forma un peor resultado.

A continuacion se realiza el calculo del gradiente de la imagen suavizada, utilizando para ellouna aproximacion del gradiente de la funcion Gaussiana.

La imagen correspondiente a la magnitud del gradiente de la funcion gaussiana tendra valoresgrandes donde la variacion de la intensidad sea grande. Por esta razon se debe eliminar aquellospixels que no tienen una magnitud alta utilizando para ello un cierto umbral.

Posteriormente se realiza un proceso de eliminacion de falsos bordes, conjuntamente a unrealzado de bordes poco definidos. Este proceso se consigue eliminando aquellos pixels que noson maximos locales.

Un punto a tener en cuenta es la eleccion de los valores de las variables que se aplican encada uno de los pasos anteriores, ya sea el valor de los umbrales o de la varianza en los filtrosgaussianos por ejemplo, ya que segun estos valores los resultados pueden ser mejores o peores.Los valores que se han tomado definitivamente para estos parametros se muestran mas adelante,en el capıtulo 8.

En resumen, la deteccion de bordes usando operadores de aproximacion del gradiente tiende afuncionar bien en los casos en que se utilizan imagenes con transiciones de intensidad claramentedefinidas y ruidos relativamente bajos [24].

El algoritmo de Canny para la deteccion de bordes se explica con mas detalle en el apendice A.

3.3. Ejemplo

Previamente a la utilizacion del algoritmo de Canny para la deteccion de bordes se probo conotros operadores como los de Sobel, pero el resultado que se obtenıa era bastante peor quecon el primero. Al aplicar el filtro de Sobel, para conseguir el gradiente y posteriormente sumagnitud y orientacion, el resultado que se obtenıa se veıa afectado por el ruido que presentabala imagen. Por este motivo se penso en aplicar previamente un filtro media o mediana parasuavizar la imagen y ası obtener mejores resultados, pero la imagen tendıa a emborronarseen vez de suavizarse. Otra opcion que se hubiese podido aplicar es la utilizacion de un filtroGaussiano previamente al filtro de Sobel, sin embargo esta posibilidad no se probo, ya quedirectamente enfocamos nuestra atencion hacia el detector de bordes de Canny.

16

3.3. Ejemplo

Un ejemplo de los resultados que se obtienen al aplicar el algoritmo de Canny se puede observaren la Figura 3.1:

(a) (b)

(c) (d)

Figura 3.1.: Resultado de aplicar el detector de bordes de Canny: (a) imagen original; (b) orien-tacion; (c) supresion no maxima; (d) histeresis de umbral

17


18

4. Deteccion de regiones candidatas

4.1. Idea general

Una idea que manejamos a la hora de detectar el codigo de barras dentro de la imagen es que((supuestamente)) los pixels que forman parte del codigo van a tener una orientacion similar omuy parecida, por ello se pretende extender la orientacion de los puntos de borde de la zonadonde se encuentra el codigo a los puntos de esta que no lo son, creando ası una region deorientacion similar que podra seleccionarse como region que contiene el codigo. Los puntos deborde representan la separacion entre los espacios y las barras del codigo, por este motivo sepretende extender la orientacion de estos puntos a aquellos puntos que no son borde y en loscuales no tenemos nada. De esta forma se consigue una zona amplia con orientacion similardonde se encuentra el codigo de barras.

Con este fin, una vez hemos conseguido el valor de la orientacion del gradiente de intensidadpara cada uno de los pixels de la imagen, operacion realizada en el paso anterior, se prosigue elproceso realizando un analisis multiresolucion de la imagen. Con esta operacion vamos a obteneruna piramide de imagenes donde cada imagen que precede a otra siempre sera de mayor tamano,es decir, se van consiguiendo imagenes de menor tamano. Pero esta operacion no solo conllevauna reduccion del tamano de la imagen progresivamente, sino que se pretende, como hemoscomentado, conseguir extender la orientacion de manera que podamos seleccionar una region dela imagen como posible zona donde se encuentra el codigo de barras por poseer, localmente, unvalor de orientacion comun.

4.2. Procedimiento

El proceso que se sigue es el siguiente: se divide el tamano de la imagen por dos, reduciendoeste hasta alcanzar un determinado tamano, por tanto cuatro pixels de la imagen en un ciertonivel pasaran a ser uno en la imagen de nivel posterior. A partir del valor de la orientacion deestos cuatros pixels se calcula la media, pero solo participan en esta operacion los pixels quepertenezcan a un punto de borde. Ası, el pixel en la imagen reducida tomara un valor para laorientacion que sera la media de los pixels de los que proviene, que seran aquellos que son puntosde borde.

Ademas, si los cuatro pixels no pertenecen a ningun punto de borde, entonces el nuevo pixelque se obtiene se etiqueta como ((no-borde)), de forma que nos va a servir para descartar zonasdonde no hay ningun punto de borde y por tanto es poco probable que el codigo de barras seencuentre en ellas.

Por tanto, si partimos de una imagen I iremos cogiendo 4 pixels de la siguiente forma:

I(i, j) I(i + 1, j)I(i, j + 1) I(i + 1, j + 1)

A partir de estos pixels se toman aquellos que son bordes y se realiza una media.

I =∑

(i,j)∈N

I(i, j)

19


siendo N el conjunto de pixels que son borde dentro de la vecindad considerada.El procedimiento implementado se muestra en el Algoritmo 1 en pseudo-codigo para una

mejor comprension de los pasos realizados. Nos aparece en el mismo la funcion Vecindad() quenos devuelve el conjunto de pixels vecinos de un determinado punto segun la vecindad indicada.Ademas esta funcion ya tiene en cuenta no acceder a puntos de fuera de la imagen. Esta funciontambien sera usada en algoritmos que aparecen mas adelante.

Algoritmo 1 Agrupamiento de la orientacion segun la vecindadEntrada: La imagen O de la orientacion de tamano M ×N , la imagen E de bordes de tamano

M ×N y la vecindad Vx × Vy utilizadaSalida: La imagen S de tamano M

Vx× M

Vy

1: for x ⇐ 1 to M with step Vx do2: for y ⇐ 1 to N with step Vy do3: numbordes ⇐ 04: Suma ⇐ 05: for all (i, j) ∈ Vecindad(x, y, Vx, Vy) do6: if E(i, j) = 1 then7: numbordes ⇐ numbordes + 18: Suma ⇐ Suma + O(i, j)9: if numbordes = 0 then

10: S( xVx

, yVy

) ⇐ ((no-borde))11: else12: S( x

Vx, y

Vy) ⇐ Suma

numbordes

Debemos senalar que este algoritmo se utiliza solo para el primer nivel, es decir, cuandopartimos de la imagen de la orientacion obtenida en el punto anterior. A partir de entonces elalgoritmo a utilizar es muy similar a este, simplemente cambia que la entrada sera la imagen desalida del Algoritmo 1 y por tanto en vez de quedarnos con aquellos puntos que son bordes nosquedaremos con aquellos que no esten etiquetados como ((no-borde)). El resto del funcionamientodel algoritmo es el mismo.

Una vez hemos obtenido la ultima imagen del escalado, es decir, hemos llegado al ultimo nivelL, realizamos ahora el proceso inverso, es decir, si hemos subido en la piramide de imagenes vamosahora a bajar, de forma que un pıxel extendera su valor a los cuatro pixels de los que provenıa.Con este proceso se pretende extender, en la zona donde se encuentra el codigo, la orientacionde los pixels que eran bordes a aquellos que no lo eran, todo ello para intentar homogeneizar laorientacion en nuestra region de interes y ası, de esta forma, poder posteriormente elegir todosestos pixels como posible zona donde pueda encontrarse el codigo de barras. El procedimientoutilizado se describe en el Algoritmo 2.

Algoritmo 2 Reconstruccion para extender la orientacionEntrada: Imagen I de tamano M ×N y la vecindad Vx × Vy utilizadaSalida: Imagen S de tamano (M · Vx)× (N · Vy)1: for x ⇐ 1 to M do2: for y ⇐ 1 to N do3: i ⇐ x · Vx

4: j ⇐ y · Vy

5: for all (i, j) ∈ Vecindad(x, y, Vx, Vy) do6: S(i, j) ⇐ I(x, y)

20

4.3. Ejemplo

Sin embargo, despues de realizar esta operacion, es decir, subir y bajar en la piramide deimagenes, la zona donde se encontraba el codigo no presentaba esa homogeneidad que se pre-tendıa y todavıa existıa demasiada variacion dentro de la zona en cuestion.

Por tanto se penso que para este proceso se podrıa coger una division mayor y en vez deun conjunto de 2 × 2 pixels de los que pasamos a uno, realizarlo de 3 × 3 o superior, pero losresultados tendıan a ser peores, es decir, cuanto mas grande es la vecindad que cogemos parareducir, los resultados empeoran, de forma que la homogeneizacion, en cuanto al valor de laorientacion de la zona donde se encuentra el codigo, es peor.

Esto puede ser debido a que al coger mas puntos para realizar la media, en la zona proxima alcodigo estamos cogiendo un numero mayor de pixels que son puntos de borde y que no pertenecenal codigo y cuyo valor afecta de manera negativa a la hora de calcular la orientacion. De algunamanera estamos provocando el proceso contrario al pretendido, ya que el valor de la orientacionde los puntos de borde de la frontera exterior al codigo y que no pertenecen al codigo de barras,dominan a los puntos de borde de dentro del codigo, provocando que su orientacion se extiendahacia dentro del codigo y reduciendo ası la region donde se encuentra este.

Otra opcion con la que los resultados que se obtuvieran podrıan ser mejores, era la posibilidadde utilizar la mediana y no la media, por su mayor robustez estadıstica. Al cambiar la media poresta operacion empezamos a conseguir lo que se pretendıa, debido, seguramente, a que la mediase podıa ver afectada, a la hora de realizarse la operacion, por un valor muy alto en cuanto alresto de valores o viceversa.

4.3. Ejemplo

Por tanto con este nuevo paso los resultados que se consiguieron eran los deseados. En laFigura 4.1 podemos observar un ejemplo de las imagenes que se obtienen en este nuevo proceso,tanto cuando subimos en la piramide, como cuando bajamos.

21


(a) (b)

Figura 4.1.: Deteccion de regiones candidatas: (a) resultado del proceso cuando subimos; (b)resultado del proceso cuando bajamos

22

5. Etiquetado y filtrado de regiones

5.1. Etiquetado de componentes conexas

Una vez realizado el paso anterior, debıamos pensar una forma de poder discriminar el conjuntode pixels que no nos proporcionan informacion relevante y quedarnos solo con aquellos que nosinteresan por contener la region de la imagen donde supuestamente se encuentra el codigo quese pretende detectar.

En busca de este objetivo se penso en utilizar algoritmos de etiquetado de componentesconexas, cuya idea basicamente consiste en agrupar pixels de una misma region dentro de laimagen, para lo cual les asigna la misma etiqueta a cada uno de ellos. Simplemente se presentabaun problema y es que la imagen a partir de la cual se aplican estos algoritmos debe ser binaria.Por ello debıamos binarizar, de alguna forma, el resultado obtenido en el proceso anterior, parapoder despues aplicar el algoritmo de componentes conexas.

El concepto de componentes conexas es el siguiente: todos los pixels que tienen un mismovalor binario “1” y estan conectados entre sı (usando 4-conectividad u 8-conectividad) por uncamino o conjunto de pixels todos con ese mismo valor binario se les asigna una misma etiquetaidentificativa, que debe ser unica de la region a la cual pertenecen los pixels y constituye suidentificador [24].

5.2. Procedimiento

Con el fin de obtener la binarizacion deseada se penso en la siguiente idea: cuando ((subimos)) enla piramide, como comentamos en el punto anterior, estamos intentando que la zona de la imagendonde se encuentra el codigo de barras se homogeinice, en cuanto al valor de la orientacion, yası, posteriormente, poder elegir todos estos pixels, con valor similar, como posible zona dondese encuentra un codigo de barras. Sin embargo, ahora cuando ((bajamos)), en lugar de extenderla orientacion a los distintos pixels segun la division implementada, podemos aprovechar parabinarizar y realizar a continuacion su correspondiente expansion.

Por tanto una vez hemos llegado al ultimo nivel (el mas alto de la piramide) nos disponemosa binarizar dicha imagen siguiendo el siguiente criterio: si la mitad de los pixels de la vecindadelegida para la division son parecidos o similares entre sı, es decir, no distan mucho en cuanto alvalor de la orientacion, segun un umbral predeterminado, entonces todos los pixels de la vecindadtendran el valor binario ((1)), si no es ası seran ((0)), al igual que si mas de la mitad de los pixels sonpuntos etiquetados como ((no-bordes)), tambien toman el valor ((0)). Una vez tenemos la imagenbinarizada, simplemente se trata a continuacion de extender esta binarizacion hasta el nivelinicial, el cual se corresponde a una imagen de tamano igual al de la imagen original. El procesode binarizacion se puede observar en el Algoritmo 3 y el proceso de extender la orientacion essimilar al que aparece en el Algoritmo 2. En el Algoritmo 3 aparece la funcion RelPixels() quesimplemente se encarga de ver la relacion existente entre los pixels de la vecindad elegida y,segun el umbral determinado, devolver una cantidad que nos indica el numero de pixels que sonsimilares entre sı.

Se probo un poco con todas las posibles variables que nos dan juego a la hora de realizar esteproceso, para ver cuales son las condiciones con las cuales se obtienen los mejores resultados.

23


Algoritmo 3 Binarizacion de un determinado nivel l de la piramideEntrada: Una imagen Ol de tamano M ×N , la vecindad Vx × Vy y un umbral USalida: Una imagen binaria S de tamano M ×N1: mitad ⇐ (V x · V y)/22: for x ⇐ 1 to M with step Vx do3: for y ⇐ 1 to N with step Vy do4: num ⇐ 05: for all (i, j) ∈ Vecindad(x, y, Vx, Vy) do6: if I(i, j) 6= ((no-borde)) then7: V ect[num] ⇐ Ol(i, j)8: num ⇐ num + 19: if num < mitad then

10: for all (i, j) ∈ Vecindad(x, y, Vx, Vy) do11: S(i, j) ⇐ 012: else13: n ⇐ RelPixels(V ect, U)14: if n > mitad then15: for all (i, j) ∈ Vecindad(x, y, Vx, Vy) do16: S(i, j) ⇐ 117: else18: for all (i, j) ∈ Vecindad(x, y, Vx, Vy) do19: S(i, j) ⇐ 0

Se realizaron pruebas con diferentes tamanos en cuanto a las operaciones de agrupamiento delos pixels vecinos 3 × 3, 5 × 5, etc., al igual que se probo a realizar el proceso de binarizacionno desde el ultimo nivel sino desde cualquier otro de los calculados. Despues de varias pruebasse pudo comprobar que utilizar una vecindad de 2 × 2 es la mejor opcion, al igual que realizarla binarizacion a partir, no desde el ultimo nivel, sino desde dos niveles menos. Ademas, otraconclusion que se obtuvo despues de probar distintas opciones, es que el nivel desde el cual esmejor empezar a binarizar depende del tamano del codigo de barras con respecto al tamano dela imagen, algo que, en nuestro caso asumimos, por su simplicidad, como constante.

Una vez obtenida la imagen binarizada del mismo tamano que la imagen inicial, una compro-bacion para asegurarnos que vamos por el camino acertado, no a nivel del algoritmo, sino comocomprobacion visual nuestra, es superponer a la imagen original esta imagen binarizada, paraver que conjunto de pixels se estan eligiendo, es decir, aquellos pixels que son la zona dondesupuestamente esta el codigo. De esta manera se puede ver si el codigo de barras esta dentro dealguna de las regiones que detectaremos con los algoritmos antes mencionados. El resultado deesta operacion se puede ver en la Figura 5.1, donde las regiones obtenidas se superponen a laimagen original que nos aparece en la Figura 3.1 (a).

Como hemos comentado, si cambiamos las opciones elegidas para realizar el proceso, el tamanode la vecindad con el que operar y el nivel a partir del cual binarizar, los resultados son bastantepeores como se puede observar en la Figura 5.2.

El algoritmo de etiquetado de componentes conexas que utilizamos es el que se denomina algo-ritmo clasico [24] (Apendice B). Este algoritmo realiza solo dos pasadas a la imagen, necesitandopara todo el proceso mantener una tabla de equivalencias de etiquetas.

El resultado del algoritmo se muestra en la Figura 5.3, donde las regiones obtenidas se hancoloreado para que se observe mejor el resultado.

Por tanto, una vez aplicado el algoritmo a nuestra imagen, solo falta, para finalizar, descartar

24

5.3. Resultados

Figura 5.1.: Imagen original con la mascara correspondiente a las regiones candidatas

(a) m = 2, Lθ = L (b) m = 3, Lθ = L− 2 (c) m = 5, Lθ = L− 1

Figura 5.2.: Distintas imagenes obtenidas segun la vecindad, de tamano m, y el nivel Lθ desdeel cual binarizar siendo L el ultimo nivel de la piramide: (a) resultado obtenido conuna vecindad 2 × 2 y binarizando a partir del ultimo nivel; (b) resultado obtenidocon una vecindad 3×3 y binarizando a partir del nivel L−2; (c) resultado obtenidocon una vecindad 5× 5 y binarizando a partir del nivel L− 1

aquellas regiones que no nos interesan y quedarnos con la que contiene el codigo de barras. Porello, en nuestro caso, nos quedaremos con la region con mayor numero de pixels, que sera, congran probabilidad, la region con mas posibilidades de contener la zona donde se encuentra elcodigo de barras.

5.3. Resultados

A continuacion mostraremos un conjunto de imagenes con el resultado obtenido al aplicar elalgoritmo de etiquetado de componentes conexas y quedarnos con aquella region con un mayornumero de pixels. De esta forma se podra observar en que casos el proceso funciona, en cuales noes exacto y que factores afectan al mismo. Antes de todo recalcar que el algoritmo en un principiose usaba para una 4-conectividad, pero se modifico para utilizar una mayor conectividad, ya quede esta manera los resultados eran mejores.

En la Figura 5.5 podemos observar que tanto en la imagen (a) como en la (b) el resultadoes bastante bueno, aunque no se incluyan unos pocos puntos del codigo dentro de la region.En la imagen (c) el codigo de barras previamente fue modificado manualmente, dibujando unalınea al principio y otra al final del mismo para ver que resultado obtenıamos. Como se puede

25


Figura 5.3.: Resultado del algoritmo de etiquetado de componentes conexas

Figura 5.4.: La region de mayor tamano de la Figura 5.3, hemos descartado las regiones que nonos interesan y nos hemos quedado con la region que contiene un mayor numero depixels

observar, la region obtenida despues de realizar el proceso incluye estas dos falsas barras, comoes logico, ya que el proceso las considera como propias del codigo. Este caracterıstica de loscodigos de barras, la facilidad con la cual es posible danarlos, conlleva la consiguiente dificultadpara los lectores que intenten descifrar dicho codigo. Pero esto ocurre tambien con otros tiposde codificacion, por ejemplo, caracteres normales, los cuales si son danados se dificulta, en granmedida, su legibilidad.

En la Figura 5.6 podemos ver tres diferentes imagenes del mismo codigo de barras, pero encada una de ellas el codigo se ha visto afectado por distintos factores que provocan el deteriorodel mismo. Como se observa aunque el codigo esta rayado, como en (a) o en (b), o inclusoemborronado, como en (c), la region que determina la zona donde se encuentra el codigo esbastante acertada y no aparecen muchos huecos dentro de la misma. Esto es debido a que lassupuestas ((manchas)) que contiene el codigo, no tienen un trazo muy intenso con lo que noafectan en gran medida al proceso, cosa muy diferente serıa si fueran mas intensas, mas oscuras,como en los siguientes ejemplos.

En la Figura 5.7 vemos como en las imagenes (a) y (b), el ruido provocado por unas rayas de

26

5.3. Resultados

(a) (b) (c)

Figura 5.5.: Resultado del proceso de localizacion ante un codigo de barras: (a,b) no danado; (c)al que se le ha dibujado una barra al principio y otra al final

(a) (b) (c)

Figura 5.6.: Diversas imagenes de un mismo codigo de barras danado por una serie de factores:(a) danado con una sola lınea; (b) afectado por mas de una lınea; (c) emborronado

trazo mas intenso que en la Figura 5.6, sı que afectan en mayor medida al proceso, provocandoque la region que contiene el codigo no sea todo lo exacta que se precisa y dificultando su posteriordecodificacion. En la imagen (c) se han complicado todavıa mas las cosas, incluyendo ademas delas rayas un elemento metalico (((clip))) encima del codigo para comprobar ası el funcionamientodel proceso ante tal situacion. Como era logico la region que se obtiene descarta la zona delcodigo donde se encuentra el ((clip)), ademas de los puntos donde se encuentran las manchas, conlo cual es muy poco probable que esta region nos pueda llevar a una posible decodificacion conexito.

27


(a) (b) (c)

Figura 5.7.: Resultado del proceso de deteccion del codigo de barras ante diversas situaciones:(a) codigo de barras rayado; (b) el mismo codigo que en la imagen anterior, pero alque se le han anadido mas modificaciones; (c) misma imagen que la anterior, peroanadiendo un elemento ajeno al codigo de barras sobre el

(a) (b) (c)

Figura 5.8.: Conjunto de imagenes a las que se les ha aplicado una transformacion geometrica:(a) rotacion de 30◦; (b) espiral de −45◦; (c) espiral de 100◦

Para una mayor comprobacion, en cuanto al buen funcionamiento de este proceso, se hatransformado una imagen digitalmente para ver que ocurre cuando introducimos algun tipo detransformacion geometrica en la misma, esto se observa en la Figura 5.8. En la imagen (a) seha aplicado una rotacion con un cierto angulo, de esta forma en la imagen aparece ademasdel propio codigo a decodificar, un trozo del mismo en una esquina. La region que obtenemoscontiene tanto el codigo, como el trozo que aparece en la esquina inferior. Esto es debido a laforma en que agrupamos los pixels con una orientacion parecida segun un cierto umbral. Como

28

5.3. Resultados

vemos esto tiene sus ventajas a la hora de capturar la zona donde se encuentra el codigo, comose observa en la imagen (b) y (c), pero por el contrario provoca que aquellas partes de la imagendonde la orientacion es muy similar, y que no pertenezcan al propio codigo de barras, tambiense puedan elegir como posible zona donde se encuentre este.

En la imagen (b) y (c) la transformacion geometrica realizada ha sido la misma en ambas, unaespecie de remolino o espiral (((swirl))), pero utilizando angulos distintos. Aunque parezca difıcil,obtenemos unas regiones que contienen el codigo de barras con bastante exactitud, sin embargola decodificacion en nuestro caso es imposible. Para poder decodificar el codigo deberıamos ircalculando las distintas orientaciones que el codigo presenta desde la primera barra hasta laultima, para ası poder ir rectificando el codigo con el angulo adecuado en cada momento yconseguir ası su decodificacion.

Despues de poder observar todos estos ejemplos parece que el proceso se comporta bastantebien, siempre y cuando el codigo no se vea afectado, en gran medida, por algun tipo de ruido,como manchas o rayas presentes en el codigo. Ademas incluso aquellas imagenes en las que seles ha aplicado una transformacion geometrica, la zona donde se encuentra el codigo se detecta,aunque su posterior decodificacion se complicarıa, y no se aborda en este proyecto.

Deberıamos comentar que se intentaron capturar imagenes que sufrieran algun tipo de defor-macion geometrica natural, realista, como puede ser que la hoja donde se encuentre impreso elcodigo de barras este doblada por ejemplo. El proceso de localizacion creemos que igual fun-cionarıa en estos casos, el problema de no poder tener imagenes para comprobarlo ha sido porculpa del enfoque. La imagen del codigo de barras, si tenıamos doblada la hoja, presentaba zonasdonde era difıcil enfocar y obtener resultados nıtidos.

Tambien pudimos comprobar que algunas pruebas en las que el codigo no presentaba ningunaraya ni mancha el resultado obtenido no era el deseado. Esto es debido a que el proceso se vebastante afectado por la calidad de la imagen, por lo que algunas mejoras para incrementar larobustez del metodo pasarıan, posiblemente, por realizar algun tipo de preproceso de la imagencon el objetivo de evitar esta dependencia.

29


30

6. Estimacion de la orientacion y rectificacion

6.1. Idea general

Todos los pasos realizados hasta este instante nos han permitido poder localizar la region dela imagen donde se encuentra el codigo de barras. Como es obvio, el codigo de barras puede estaren cualquier posicion dentro de la imagen, al igual que puede presentar cualquier orientacion, loque dificulta su localizacion.

Por tanto, debemos calcular la orientacion que presentan los puntos de borde que contienela region susceptible de contener al codigo y que hemos obtenido en el paso anterior. Una vezconocida esta orientacion simplemente debemos rectificar la imagen y conseguir a continuacionuna imagen que solo contenga el codigo. Esta subimagen sera binarizada para su posteriordecodificacion.

6.2. Procedimiento

El procedimiento utilizado para averiguar el angulo que debemos aplicar en la rotacion dela imagen y que de esta manera se nos quede en sentido horizontal, es decir, con las barrasverticales, ha sido el siguiente: de todos los puntos de borde que se encuentran en la region que seha seleccionado, que es donde se encuentra el codigo, nos quedamos con el valor de la orientacionde cada uno de ellos y calculamos la mediana para conseguir el valor mas representativo de laorientacion en esa zona. Se calcula la mediana en vez de la media, ya que esta primera resultaser mas robusta.

Una vez obtenemos la orientacion que representa a todo el conjunto de puntos que conformanla zona donde se encuentra el codigo, simplemente tenemos que utilizarla para rotar la imagenoriginal una cantidad igual al angulo estimado.

(a) (b) (c)

Figura 6.1.: Rotaciones con la orientacion estimada usando la mediana: (a) imagen original; (b)imagen original rotada; (c) region donde hemos estimado que se encuentra el codigo

Una vez realizada la rotacion, lo que se pretende es obtener una imagen de tamano igual a lacaja de mınima inclusion [13] que contiene el trozo de imagen original rotada que se corresponde

31

6. Estimacion de la orientacion y rectificacion

al codigo de barras. Para ello debemos basarnos en la region obtenida en el paso anterior y en laimagen original rotada, siendo el resultado el que se muestra en la imagen (a) de la Figura 6.2.

Una vez obtenida esta nueva imagen, solo nos queda binarizarla para facilitarnos su posteriordecodificacion. Con el objetivo de obtener una mejor binarizacion realizaremos una ecualizaciondel histograma [12] que nos permitira conseguir un mayor constraste entre las barras negras ylos espacios como se puede observar en la imagen (b) de la Figura 6.2.

(a) (b)

Figura 6.2.: Caja de mınima inclusion que incluye la region donde hemos determinado que seencuentra el codigo: (a) antes de la ecualizacion del histograma; (b) despues de laecualizacion del histograma

Para la obtencion del umbral a partir del cual realizar la binarizacion existen diversos metodosautomaticos de busqueda de este [11], como el algoritmo de Otsu [8], que es el empleado ennuestro caso. El umbral que se obtiene con este metodo se considera aquel punto que parte lospixels de una imagen en dos clases de niveles de gris C0 = {0, 1, . . . , t} y C1 = {t+1, t+2, . . . , L},siendo L el valor maximo de niveles de gris y t el umbral optimo que maximiza la separabilidadde estas dos clases. El metodo se explica con mas detalle en el Apendice C.

De esta manera, el resultado que se obtiene despues de la binarizacion, utilizando como umbralel obtenido con el algoritmo de Otsu, es el que aparece en la Figura 6.3.

Figura 6.3.: Binarizacion utilizando el algoritmo de Otsu

Tanto la ecualizacion del histograma como la busqueda automatica del umbral, mejoran losresultados de la binarizacion, ya que en un primer momento no usabamos estas tecnicas, siendoademas el umbral un valor fijo, con lo cual se obtenıan unos resultados bastante peores. Esto sepodra comprobar, con mayor detalle, en el siguiente capıtulo.

32

7. Decodificacion

7.1. Introduccion

Durante la fase de decodificacion surgieron bastantes problemas que nos hicieron pensar quela decodificacion no es un proceso tan trivial como en un principio pueda parecer, una vezconseguida la localizacion del codigo dentro de la imagen.

Mientras se pensaba en un procedimiento que nos permitiese decodificar el codigo obtenidoen las fases anteriores, surgio la idea de utilizar tecnicas relacionadas con el reconocimiento delhabla. Dentro de estas tecnicas encontramos los modelos de Markov [25], que a base de entre-namiento consiguen identificar palabras de una frase analizando los fonemas que las caracterizan.Sin embargo dominar esta tecnica requiere de mucho tiempo, ademas una vez determinados losautomatas que conforman el modelo se necesita de un aprendizaje, con el consiguiente gasto detiempo que ello conlleva y sobretodo, no se tenıa la certeza de que fuera a funcionar en nuestrocaso. Debido a estas razones, y a la limitacion del tiempo que tenıamos para la realizacion denuestro proyecto, se descarto su uso.

Otra tecnica relacionada con la anterior es la tecnica DTW (Dynamic Time Warping) [23, 15].Este metodo intenta el reconocimiemto de palabras conectadas en una frase, pero al contrarioque en los modelos de Markov no requiere de entrenamiento. Llego a implementarse un algoritmorepresentativo de esta tecnica, pero adaptado a nuestro caso en particular, es decir, en vez deconseguir descifrar palabras dentro de una frase intentamos descifrar dıgitos de una secuenciabinaria. Los resultados no fueron los deseados y se desestimo esta opcion.

Otro motivo que provoco que desestimaramos estas dos opciones es que son metodos dema-siado generales para lo que se pretende en este proyecto. Tiene sentido reconocer palabras conestas tecnicas, ya que las palabras pueden sufrir deformaciones segun quien las pronuncia, elacento, etc. Nosotros no vamos a alargar nuestro codigo, ni sufrira deformaciones similares a lasindicadas, solo nos afecta la correcta estimacion de la orientacion para la rectificacion del codigode barras. Por tanto tendrıa sentido utilizar estas tecnicas, si nuestro codigo si que sufriese esaserie de transformaciones que provocasen su alargamiento, por ejemplo.

Incluso se penso en utilizar la tecnica de crestas y valles (ridges and valleys) [21], utilizada enciertos campos, como la medicina o en el procesamiento de huellas digitales. Para ello se utilizanestas crestas o valles que aparecen en la imagen como caracterısticas geometricas utiles en elanalisis de imagenes.

Uno de los trabajos relacionados con los codigos de barras [28], del cual obtuvimos bastanteinformacion y que mencionamos en el primer capıtulo de esta memoria, intentaba decodificarel codigo de barras de la siguiente forma: una vez obtenida la region de interes se extraıa de lamisma una onda donde aparecerıan crestas y valles correspondientes a los espacios y las barrasdel codigo. La onda se umbraliza para conseguir que los elementos de las barras y espacios delcodigo se distingan con claridad. Se extraen elementos de la onda segun las anchuras que estospresentan en el tipo de codigo a interpretar. Finalmente, conociendo lo que ocupa un caractersegun el tipo de codificacion, se van obteniendo los distintos caracteres que contienen el codigoy se decodifican.

33

7. Decodificacion

7.2. Procedimiento

La decodificacion se basa en el conocimiento del tipo concreto de codigo de barras que seutiliza, en nuestro caso el codigo EAN-13. Por este motivo recordar que la forma de codificaciondel codigo EAN-13 se explica en el Apendice D pagina 57 de esta memoria, por lo que en casode duda, ante algunos de los comentarios que vamos a mencionar sobre el tipo de codificacion,sirva este apartado como guıa o ayuda.

En cuanto a la decodificacion del codigo de barras podemos aprovechar las posibles ventajasque se nos presenten, es decir, podemos utilizar el conocimiento ((a priori)) que tenemos, parasimplificar el problema. En nuestro caso en particular, la ventaja primordial es que nosotros pre-tendemos decodificar codigos de barras utilizados para codificar la numeracion ISBN de los librosy, debido a ello, conocemos de antemano que los codigos de barras de este tipo de publicacionesempiezan con los dıgitos 978. Sabemos pues que el primer dıgito es el 9 y, consecuentemente,la disposicion en cuanto al tipo de codificacion que presentara la primera parte del codigo, esdecir, el dıgito 9 se corresponde con la secuencia ABBABA. Por todo ello podemos determinar quenuestro codigo presentara la siguiente forma (Tabla D.4 pagina 59):

9 ABBABA CCCCCC

donde cada dıgito se codifica segun el tipo de codificacion que se ha determinado.Para decodificar nuestro codigo vamos a trazar una serie de lıneas imaginarias horizontales

sobre la imagen binaria centrada en el codigo obtenida en la fase anterior, a modo de los lectoreslaser, quedandonos con el valor de cada pıxel por el que se atraviesa. El trazar mas de una lıneapersigue una mayor seguridad a la hora de que la decodificacion sea correcta, por ello el numerode lıneas que vamos a realizar sera igual a la altura de la imagen.

Las lıneas que obtengamos debemos poder dividirlas en segmentos correspondientes a cadauno de los posibles patrones que debemos encontrar, es decir, patron inicial y final, el patronintermedio y el correspondiente a cada uno de los dıgitos que componen el codigo. El patroninicial y el final estan formados por tres modulos (101), donde un modulo como se explico en elapartado 2.2 (pagina 7), es la unidad mınima o basica de un codigo. El patron intermedio, por suparte, esta formado por cinco modulos (01010) y cada uno de los dıgitos esta compuesto por 7modulos. Con esta informacion, si sabemos que en el codigo nos aparecen 12 dıgitos codificados,ya que el primero no lo esta, tendremos una cantidad total de modulos de 95:

Inicio Seis dıgitos Intermedio Seis dıgitos Fin Numero de modulos3 6 · 7 5 6 · 7 3 95

Pero las lıneas que calculemos van a tener una cantidad de pixels que dependera de la escalaa la que este el codigo dentro de la imagen. Por ello debemos calcular esta deformacion y vercomo nos afecta en nuestro caso, calculando cuantos pixels por modulo tenemos, es decir:

β =n

M

donde n es la cantidad total de pixels que conforman el codigo en nuestra imagen, β sera elnumero de pixels por modulo y M es la cantidad total de modulos que aparecen en un codigo,que en nuestro caso, como hemos visto, vale 95.

Una vez obtenemos este dato podemos averiguar la relacion de pixels que se corresponde concada uno de los patrones antes mencionados, simplemente multiplicando el numero de modulospor el numero de pixels por modulo β, es decir, el tamano de un dıgito sera el valor que seobtenga de multiplicar el numero de pixels por modulo β por 7 modulos que forman un dıgito.

34

7.2. Procedimiento

Con estos datos podemos ir dividiendo la lınea y quedarnos con los pixels correspondientesa cada dıgito dentro de la lınea e intentar averiguar cual es este dıgito. Actuaremos de lasiguiente manera: si sabemos que un dıgito codificado con la codificacion de tipo A va a seguirun determinado patron, teniendo una cantidad de ceros seguida de otra de unos, luego mas cerosy por ultimo otra vez unos, podemos determinar el tamano maximo que nos va a ocupar undıgito de la siguiente manera:

γ = m · β,

si β (numero de pixels por modulo) es 2 y m = 7, siendo m el numero de modulos que formaun dıgito, γ = 14, siendo γ el numero maximo de pixels que ocupara un dıgito. Dentro de estetamano buscaremos el patron que hemos comentado (0101, con una cierta cantidad en cada casode ceros y unos). Podemos encontrar este patron dentro de los 14 pixels y que el ultimo pıxelsea el numero 14 o no, y sea el 13 o el 12, simplemente donde nos quedemos sera el pıxel decomienzo del siguiente dıgito y a partir de este empezaremos a buscar el patron correspondienteal siguiente dıgito en los 14 pixels que le siguen. Para un mejor entendimiento veamos esteejemplo,

. . . 11 00001111000111︸︷︷︸14

0001100001111︸︷︷︸13

0︸︷︷︸14

000 . . .

Como se observa, el primer dıgito ocupa los 14 pixels que puede tener como maximo, sinembargo el segundo dıgito no ocupa los 14 pixels sino 13, luego la posicion en la que empezara elsiguiente dıgito sera el pıxel que se encuentra dentro de una caja y no el subrayado, como hubiesesido si el dıgito ocupase el maximo numero de pixels posible.

Vemos que, a pesar de determinar las cantidades de pixels que cogemos para un dıgito concreto,este valor puede tener una pequena variacion con lo que realmente ocupa el patron correspon-diente al dıgito, debido a la perdida de informacion con los decimales y sus redondeos. Por estarazon buscamos los diferentes patrones o cambios que deben aparecer en cada caso dentro de lacantidad de pixels que hemos calculado y si se encuentra antes del tamano maximo que se hadeterminado, entonces ese punto en concreto sera el principio del siguiente dıgito.

Una vez tenemos el conjunto de unos y ceros correspondiente a cada dıgito, como sabemoscon que tipo de codificacion, A, B o C, se ha codificado, simplemente tenemos que averiguar conque dıgito se corresponde. Para ello vamos a calcular la distancia que presenta este conjunto concada uno de los dıgitos del tipo correspondiente de la siguiente forma: podemos representar laforma de codificacion de un dıgito en vez de como un patron de unos y ceros, como un patronde numero de modulos que representan estos unos y ceros, es decir,

Dıgito Codificacion A Numero de modulos0 0001101 3211

Como vemos, tenemos tres modulos correspondientes a un espacio ancho, dos modulos corres-pondientes a una barra ancha, un modulo para un espacio estrecho y un modulo para una barraestrecha.

Siguiendo esta idea lo mismo haremos nosotros para el conjunto de ceros y unos que obtenga-mos de la lınea calculada y que representan un dıgito, para a continuacion emplear la formulade la suma de cuadrados y calcular para que dıgito esta distancia es menor.

n∑i=1

(xi − yi)2

35

7. Decodificacion

siendo xi cada uno de las cantidades correspondientes al numero de modulos del conjunto deunos y ceros obtenidos de la lınea calculada, yi cada una de las cantidades de modulos de undıgito en la codificacion correspondiente y la variable n que se corresponde al valor 4 ya quetenemos este numero de cambios en un dıgito.

Para que se entienda mejor este paso vamos a explicarlo con un ejemplo. Si tenemos el siguienteconjunto de pixels para un dıgito en concreto:

00001111000111

calculamos el numero de unos y de ceros que contiene el conjunto de la siguiente manera,

0000︸︷︷︸4

1111︸︷︷︸4

000︸︷︷︸3

111︸︷︷︸3

a continuacion dividimos el numero de unos y ceros por el numero de pixels por modulo β, deesta forma obtendremos el valor equivalente de modulos en cada caso.

0000︸︷︷︸4β

1111︸︷︷︸4β

000︸︷︷︸3β

111︸︷︷︸3β

Suponiendo que β = 2 obtendrıamos,

0000︸︷︷︸2

1111︸︷︷︸2

000︸︷︷︸1,5

111︸︷︷︸1,5

Ahora simplemente debemos aplicar la formula de la suma de cuadrados con los 10 dıgitos conlos que debemos comparar y con aquel que el resultado sea menor, sera el dıgito representadopor el conjunto de unos y ceros que se esta analizando.

Para todas las lıneas que realizamos, una vez decodificadas, calculamos el checksum o caracterde verificacion segun la codificacion EAN-13, con el objetivo de asegurarnos que la decodificaciones correcta. En caso de no ser ası ese resultado se descarta por no ser correcto y solo se tienenen cuenta para el resultado final aquellas lıneas donde el checksum sea correcto. Un pequenoproblema que se nos presenta es que en ocasiones aparecen combinaciones de dıgitos que con-siguen que el checksum sea correcto, pero sin embargo el codigo no representa al que aparece enla imagen, provocando que el resultado final no sea correcto.

Como explicaremos a continuacion, los dıgitos finales que elegiremos como resultado se puedenobtener mediante diferentes metodos, teniendo en cuenta todas las lıneas obtenidas con unchecksum correcto.

Una forma es calcular el numero de veces que aparece un dıgito en una determinadaposicion y elegir como mas probable aquel que mas veces se repite en esa posicion enconcreto.

Otra posible opcion es utilizando probabilidades, es decir, calcularemos a partir de lasdistancias que hemos calculado previamente la probabilidad que presenta un dıgito de serel correcto y nos quedaremos con aquel dıgito cuya probabilidad sea mas alta. La obtencionde estas probabilidades se realiza a partir de la siguiente formula:

p = e−d

σ2

donde p sera la probabilidad que presentara un valor de ser el correcto, d es la distanciaobtenida con la suma de cuadrados para ese determinado valor y σ2 es la varianza delconjunto de valores obtenidos con la suma de cuadrados para cada uno de los dıgitos conlos que se ha realizado la operacion.

36

7.3. Resultados

Otra forma de obtener el resultado es combinando la probabilidad con la confianza, me-diante su producto y eligiendo aquel dıgito para el cual se obtenga un mayor valor de estaoperacion. Cuando nosotros trazamos una lınea, esta puede cruzar por una zona que no sehaya elegido como perteneciente al codigo, por ser una mancha o cualquier otra clase deruido, pero que, sin embargo, puede ser una zona mınima que igual permita al resto de lalınea obtener un codigo valido. Ademas los pixels que conforman esta zona estan etiqueta-dos como puntos de la imagen que no contienen informacion valida del codigo. Por tantocuando realizamos las distintas divisiones de la lınea para compararlas con los dıgitos deltipo de codificacion que se corresponda para cada posicion en concreto, puede ocurrir queun conjunto de esos pixels contenga algunos etiquetados como puntos con informacion novalida. Por ello la confianza nos vendra dada por el porcentaje de puntos con informacionvalida dentro del conjunto de pixels.

Como ultima opcion estudiada es una igual que la anterior pero en vez de coger el valormaximo, calculamos la mediana y nos quedamos con el valor que se obtenga.

Como existen diferentes caracterısticas o informacion a la hora de la decodificacion del codigo,se debe de alguna forma intentar clasificar y combinar esta informacion [19], con la intencion deofrecernos ayuda a la hora de interpretar el codigo. En nuestro caso ha sido una tarea bastantecomplicada y se opto por lo siguiente: una vez calculados los cuatro, elegimos aquel resultadocuyo codigo sea correcto en cuanto al calculo del checksum y ademas empiece por 978 que, comocomentamos al principio de este apartado, son los tres primeros dıgitos con los que empieza uncodigo ISBN. Veamos un ejemplo:

Tabla 7.1.: Ejemplo de posibles resultados segun la opcion elegidaTecnica N.o decodificado Checksum ¿Inicio 978?N.o veces aparicion 9788428323086 Correcto SıMaxima probabilidad 9478228323088 Correcto NoMaxima probabilidad × confianza 9488428323086 Incorrecto NoMediana probabilidad × confianza 9788428323085 Incorrecto Sı

En este ejemplo vemos el resultado obtenido con cada una de las opciones antes mencionadas,por tanto segun estos resultados elegirıamos la primera opcion.

7.3. Resultados

A continuacion se muestra una serie de imagenes junto al codigo que hemos conseguido de-codificar. En caso de haber algun dıgito del codigo erroneo, este aparece dentro de una cajaindicando que no era el correcto. Ası, de esta manera, se podra apreciar aquellos casos en losque el metodo funciona correctamente y en cuales falla uno o varios dıgitos.

Como podemos observar en la Figura 7.1, se ha conseguido para cada una de esas imagenesdecodificar el codigo y obtener los distintos dıgitos que lo componen sin ningun error. Pero estasimagenes pertenecıan a codigos sin ningun tipo de deterioro provocado por rayas o manchas,por ello vamos a analizar como se comporta el metodo ante situaciones menos favorables.

El comportamiento del metodo ante codigos deteriorados lo podemos observar en la Figura 7.2donde nos aparecen codigos con algun tipo de marca que dificulta su decodificacion, sin embargola solucion obtenida ha sido la deseada sin ningun tipo de error. Esto es debido a que las manchasque presenta el codigo de barras no son lo suficientemente fuertes como p o marcadas para evitarla correcta decodificacion del mismo. En cambio, en ciertos casos como los que mostramos en la

37

7. Decodificacion

9788428323086 9789706860507 9788428328647

Figura 7.1.: Distintas imagenes con el codigo que se ha obtenido al aplicar nuestro metodo

Figura 7.3, el resultado final sı que presenta algun dıgito que no se corresponde con el dıgito delcodigo en cuestion.

9788428324304 9788428326360 9788428326360

Figura 7.2.: Una serie de imagenes en las que el codigo sufre alguna alteracion en cuanto apresentar rayas o manchas sobre el, pero la decodificacion final es completametecorrecta

9788428326 8 77 978842 79 27336 97884 1 8328111

Figura 7.3.: Conjunto de imagenes en las que la decodificacion del codigo de barras presentaalgun dıgito erroneo

Pero no siempre el resultado que se obtiene es aceptable. A veces, el resultado conseguidopresenta un numero de dıgitos la mayorıa de ellos erroneo, como se observa en la Figura 7.4.

Este mal funcionamiento es debido a la intensidad de las marcas que presenta el codigo, quecomo comentamos en apartados anteriores, afecta a la hora de la deteccion de la zona donde seencuentra este. Esta mala deteccion provoca que esta ultima fase de decodificacion sea erroneaal no tener la region que contiene al codigo la suficiente informacion, de manera que permita ladecodificacion del codigo de barras con exito.

38

7.4. Analisis de robustez

9 0 8 7 42 4 3 42 3 63 978 51121 2864 0 9 34747551 8 301

Figura 7.4.: Imagenes donde el metodo no conseguıa los resultados deseados

De forma global, los resultados que se han obtenido, basandonos en un conjunto de imagenesde prueba, han sido los que se muestran en la Tabla 7.2. Solo comentar, que de las 15 imagenesen las que no se consiguio obtener el codigo correcto, casi la mitad de ellas, mas exactamente en7, el codigo solo presentaba un dıgito erroneo.

Tabla 7.2.: Comportamiento del metodo

ResultadosCaso analizado N.o imagenes Correcto Incorrecto Porcentaje

Limpia 10 7 3 70Danada 24 12 12 50Total 34 19 15 56


En este apartado se van a presentar una serie de ejemplos o experimentos para comprobarhasta que punto el metodo puede ser fiable, o simplemente con el proposito de dejar claro ciertosaspectos que creemos pueden resultar de interes.

Automatizacion del proceso de binarizacion

Como comentamos en el capıtulo anterior, previamente a la binarizacion se realiza una ecua-lizacion del histograma, Este paso junto a la utilizacion del metodo de Otsu para encontrar elumbral a partir del cual binarizar, mejoran dicha binarizacion y por consiguiente, la posteriordecodificacion. En la Figura 7.5 se muestra el resultado que se obtiene tanto sin ecualizar ycon un umbral fijo, como el mismo resultado ecualizando el histograma y aplicando Otsu paraencontrar dicho umbral.

Se puede observar que la subimagen que se obtiene del codigo de barras sin haber realizadola ecualizacion y con un umbral fijo, es peor que en el otro caso comentado. Ademas la decodi-ficacion no tiene exito, debido a que la imagen binarizada no es lo bastante buena para poderser decodificada correctamente. De ahı la importancia, tanto de la ecualizacion previa de laimagen como del calculo automatico del umbral a partir del cual binarizar, ya que si este es fijo,en ciertas imagenes nos va a resultar adecuado, pero en otras no. Debido a esto no podıamosencontrar un valor que fuese adecuado para todos los casos, por lo que se penso en el metodode Otsu para evitar este contratiempo.

39

7. Decodificacion

9789687529714 9769687 0151 1 5 978968752914(a) (b) (c)

Figura 7.5.: Obtencion de la subimagen binarizada centrada en el codigo de barras: (a) Imagenoriginal; (b) obtenida sin ecualizar el histograma y con un umbral fijo de 110; (c)previamente se ha ecualizado el histograma y se ha aplicado Otsu para calcular elumbral con el cual binarizar

Influencia del error de la estimacion de la orientacion

Otro aspecto que resultarıa de interes analizar es hasta que punto influye el valor que se estimade la orientacion con el cual se rectifica la imagen. Es decir, si la estimacion de la orientacion esmuy exacta podremos conseguir rotar la imagen de manera que se obtenga el codigo totalmentehorizontal, la variacion que este valor presente nos llevara a obtener un codigo de barras conuna cierta inclinacion hacia un lado o hacia el otro como se puede observar en la Figura 7.6.

(a) (b) φe = 0 (c) |φe| = 10◦

Figura 7.6.: Subimagenes que se obtienen segun el error en la estimacion de la orientacion (φe)realizada: (a) imagen original; (b) estimacion de la orientacion practicamente per-fecta; (c) estimacion de la orientacion erronea en unos 10◦

Por ello se ha realizado un experimento con el objetivo de comprobar cual es el intervalo enel que nos podemos mover en cuanto a la estimacion de la orientacion. De esta forma podremosconocer tambien la robustez del metodo cuando se tiene que decodificar un codigo que no seencuentra totalmente horizontal, sino que presenta una cierta inclinacion mas o menos exagerada.

En la Figura 7.7 se muestra una grafica que relaciona el nivel de inclinacion que puede pre-sentar el codigo una vez rectificado con respecto al numero de dıgitos acertados a la hora de ladecodificacion. Como es logico, en el eje de abcisas, el valor 0 se corresponde a una estimacionde la orientacion perfecta, con lo que se obtendrıa un codigo de barras totalmente horizontal.El resto de valores se corresponde al aumento del error en la estimacion de la orientacion quepresenta el codigo de barras, hacia un lado o hacia el otro.

En la grafica se observa que podemos tener un error en la orientacion bastante elevado, dealrededor de 10 grados, tanto en un sentido como en otro. A partir de este error el numero

40


0

2

4

6

8

10

12

14

-20 -15 -10 -5 0 5 10 15 20

acie

rtos

[dig

itos

corr

ecto

s]

error orientacion [grados]

Figura 7.7.: Efecto que provoca una estimacion de la orientacion erronea a la cantidad de dıgitosacertados en la decodificacion

de dıgitos acertados disminuye, viendose mas afectado el resultado en un sentido que en elotro. Suponemos que la razon por la cual puede suceder esto es debido a la imagen utilizadapara realizar el experimento, la imagen (a) de la Figura 7.6, en la cual podemos observar quenos falta un trozo de codigo de barras en la parte inferior derecha. Como en la decodificaciontrazamos lıneas horizontales para obtener la secuencia binaria que despues decodificamos, llegaun momento que la orientacion estimada es tan erronea que conlleva una inclinacion excesivadel codigo, provocando que las lıneas que nosotros trazamos no consiguan atravesar totalmenteeste, es decir, no consigan pasar por todas las barras y espacios que lo forman. Esta situacionse ve agravada cuando el codigo de barras se inclina hacia el lado contrario del trozo de codigoque nos falta, provocando ası su mala decodificacion.

Influencia del tamano relativo del codigo de barras

Pero nuestro metodo tambien se puede ver afectado por la influencia del tamano relativo delcodigo de barras dentro de la imagen. Por esta razon se ha realizado un escalado de la imagencon distintos factores, con el objetivo de aumentar o disminuir el tamano del codigo y podercomprobar ası, hasta que punto el metodo implementado consigue ser efectivo, en cuanto a laobtencion de la region que contiene al codigo en la fase de localizacion del mismo.

En la grafica presente en la Figura 7.8 se observa no solo hasta que nivel podemos aumentar odisminuir el tamano del codigo y que la localizacion sea buena, sino tambien el numero de dıgitosacertados que tenemos en cada caso. La lınea discontinua corresponde al numero de dıgitosacertados, mientras que la lınea continua representa la validez de la localizacion conseguida.Cabe destacar que la determinacion de que una localizacion es buena o no, es cualitativa ysubjetiva, mientras que el numero de dıgitos acertado es una variable cuantitativa y objetiva.Por esta razon, cuando la localizacion es buena, se le asigna el maximo valor de dıgitos acertados13 y cuando no lo es su valor es 0, es como si 13 se correspondiese a ((OK)) y 0 a ((no OK)). Este

41

7. Decodificacion

paso se ha realizado para poder tener las dos comparativas en una misma grafica.

0

2

4

6

8

10

12

14

0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8

loca

lizac

ion

[OK

-no

OK

},aci

erto

s [d

igito

s co

rrec

tos]

factor de escala

localizacion codigo

digitos acertados

Figura 7.8.: Estudio para comprobar como afecta el escalado a la localizacion del codigo debarras y a la cantidad de dıgitos acertados en la decodificacion

Segun estos resultados se tiene mejor funcionamiento de la localizacion de la region candidatade contener al codigo, si se reduce el tamano del mismo que si este se ve aumentado. Esto esdebido a que si aumentamos el tamano del codigo tambien aumentamos el tamano de las barras ylos espacios, con lo cual, a la hora de extender la orientacion, estas distancias existentes entre losbordes provoca que la orientacion de los puntos de borde no se extiendan a todos los puntos de lazona del codigo que no lo son, y por tanto, provoca que se falle en la fase de localizacion. Ademas,tambien se observa que en cuanto al intervalo donde la localizacion es correcta, no siempre seaciertan todos los dıgitos del codigo, por lo que se deduce que una acertada localizacion delcodigo no siempre provoca una acertada decodificacion del mismo. Esto nos lleva a pensar quela decodificacion deberıa ser mejorada de alguna forma, para que no ocurriese esto y sucedieralo contrario, que una buena localizacion provocara una decodificacion correcta.

Tambien recalcar que pese a todo, la localizacion consigue funcionar incluso con cambios deescala tan importantes como los que se consiguen aplicando un factor de 0.7 y 1.2.

En la Figura 7.9 se puede observar la misma imagen a la cual se le ha aplicado dos factoresde escala distintos, unos de ellos aumenta la imagen y el otro la disminuye, junto al codigo queposteriormente se consigue decodificar.

Influencia del numero de lıneas empleadas en la decodificacion

Para finalizar, resultarıa tambien interesante conocer como afecta a la hora de la decodificacionel numero de lıneas que se realizan para la misma. Con este motivo se han utilizado las dosimagenes presentes en la Figura 7.10, en las cuales se observa como, una de las dos, presentauna mancha, mientras que la otra se encuentra totalmente limpia sin ningun tipo de manchao raya. Realizaremos un experimento y que consistira en utilizar para la decodificacion unporcentaje de las lıneas que conforman la altura de la subimagen centrada en el codigo. El

42


(a) (b)

9788428323086 978 3661402308(c) (d)

Figura 7.9.: Imagenes escaladas: (a) se ha aplicado un factor de 0.8, con lo que se reduce el codigode barras; (b) se ha aplicado un factor de 1.3, con lo que se aumenta el codigo debarras; (c) region obtenida al realizar el proceso de localizacion del codigo juntoal conjunto de dıgitos del codigo de barras decodificado correctamente; (d) regionobtenida para la imagen junto al codigo decodificado erroneamente

resultado del experimento se puede observar en la grafica que aparece en la Figura 7.11. La lıneacontinua pertenece al resultado obtenido para la imagen (a) de la Figura 7.10, mientras que laotra pertenece al resultado obtenido para la imagen (b) de la misma figura.

9788428323086 9788497320658(a) (b)

Figura 7.10.: Imagenes analizadas: (a) limpia; (b) presenta una mancha

Como podemos observar en una imagen limpia no importa la cantidad de lıneas que utilicemosa la hora de la decodificacion, ya que tanto con un numero elevado de lıneas (en este caso el100 % se corresponde a 118 lıneas) como con un numero mas pequeno conseguimos decodificar el

43

7. Decodificacion

codigo correctamente. Sin embargo, cuando la imagen se ve danada por algun tipo de mancha,esto no ocurre ası, y sı que afecta el numero de lıneas que analicemos. Hasta que no llegamosa un 40 % (en este caso el 100 % se corresponde a 79 lıneas) no se obtiene la decodificacion delcodigo de barras con exito. Por tanto, podemos concluir que para no malgastar recursos con un40 % de lıneas que se utilicen en la fase de la decodificacion serıa suficiente, pero como nosotrosno conocemos que tipo de manchas van a presentar los codigos que se analicen, debemos realizarel maximo numero de lıneas posible para su correcta decodificacion.

0

2

4

6

8

10

12

14

10 20 30 40 50 60 70 80 90 100

acie

rtos

[dig

itos

corr

ecto

s]

numero de lineas [%]

imagen 7.10 (a)

imagen 7.10 (b)

Figura 7.11.: Efecto que provoca el numero de lıneas empleado para la decodificacion a la can-tidad de dıgitos acertados en la misma

44

8. Sistema experimental

En este punto simplemente vamos a comentar el material utilizado para la realizacion delproyecto, al igual que mencionaremos ciertas restricciones que se han adoptado durante la im-plementacion del mismo. Tambien creemos necesario comentar los valores que se han fijado paraalgunas parametros utilizados en los algoritmos y el motivo por el cual se ha adoptado ese valor.Por ultimo mostraremos el tiempo de ejecucion del algoritmo, desglosado para cada una de lasfases que lo componen.

8.1. Informacion general

En primer lugar comentar que las imagenes de los codigos de barras empleadas en el proyectohan sido tomadas del catalogo universitario de libros de matematicas, ciencias, ingenierıa ycomputacion del ano 2004 de la editorial THOMSON. La camara con la cual se ha recopilado esteconjunto de imagenes era una camara SONY DFW-VL500 de color digital. Como caracterısticaa destacar comentar que la propia camara contiene unos botones que permiten realizar un zoomy un enfoque de la imagen de forma manual, sin tener que determinar ningun parametro desde laaplicacion con la que se este utilizando la camara. Tambien se hicieron pruebas con otra camara,una camara digital IEEE 1394, y usando para la visualizacion de las imagenes la aplicacionCoriander 1.0.0 [1], pero finalmente solo se ha usado una de las imagenes que de esta forma setomaron.

Para la adquisicion de imagenes se ha empleado un conjunto de funciones de Matlab 7.0 yque se explican en su correspondiente manual [17]. A continuacion se presenta un ejemplo de lasfunciones utilizadas para la captura de una imagen, con el objetivo de poder grabarla luego adisco:

vid=videoinput{’dcam’,’Y422_320x240’);vid.ReturnedColorSpace=’RGB’;preview(vid);im=getSnapShot(vid);imshow(im);imwrite(im,’barcode.pgm’);

Por ultimo solo comentar que el metodo presentado en este proyecto se ha implementadoen C++ bajo el sistema Suse Linux 9.2. Como cabe pensar, se ha utilizado en el mismo unalibrerıa de procesamiento de imagenes, en este caso la CImg [29] en su version 1.0.8, al igual queun conjunto de programas de visualizacion y conversion de imagenes como el xv o el convert.El convert se ha utilizado sobretodo para conversion de imagenes y para la realizacion de lastransformaciones geometricas que se pueden ver en la Figura 5.8 (pagina 28).

45


8.2. Restricciones

Aunque como se ha comentado, el codigo de barras puede presentar cualquier orientacion, unarestriccion que se ha fijado en cuanto a nuestro proyecto, ha sido que la orientacion del codigodebe encontrarse en un intervalo de entre −90◦ y 90◦. Esto es debido a que si no fuera ası sedificulta en gran medida la decodificacion del codigo de barras. El motivo es que a la hora dela rotacion, la orientacion que presentan las barras puede provocar que el codigo se quede ensentido inverso, es decir, boca abajo, y la decodificacion de esta forma se complica bastante.

Debemos recalcar que no es lo mismo la orientacion del codigo de barras que la orientacionde las barras presentes en el mismo, ya que cuando el codigo de barras se encuentra en sentidohorizontal la orientacion del mismo son 0◦, pero por el contrario las barras presentan un angulode 90◦.

El tamano de todas las imagenes con las cuales se ha probado el metodo era de 320 × 240pixels, simplemente para tener un tamano base y por simplicidad, aunque se han hecho pruebascon unas pocas imagenes de tamano superior obteniendo resultados similares. Para finalizarcomentar que el tamano del codigo de barras con respecto a la imagen siempre ha sido mas omenos parecido dentro de un intervalo.

8.3. Valores por defecto

Durante todo el proceso un conjunto de parametros, que creemos importantes, han mantenidoun valor fijo debido a una serie de razones que explicamos en este apartado. Estos valores semuestran a continuacion en la siguiente tabla:

Tabla 8.1.: Parametros con valores por defecto

Fase Parametro Significado ValorDeteccion de bordes σ Varianza 0.5Deteccion de bordes t1 Umbral usado en la histeresis 20Deteccion de bordes t2 Umbral usado en la histeresis 40Etiquetado y filtrado de regiones U Umbral (dif. max. en orientacion) 10

Para los parametros σ, t1 y t2 utilizados en el algoritmo de Canny para deteccion de bordes, seha fijado un determinado valor despues de realizar una serie de pruebas con el objetivo de obtenerlos mejores resultados posibles. Se consulto diferente bibliografıa para comprobar cuales eranlos valores mas adecuados a utilizar en estas variables, sin embargo no se consiguio determinarque valores a usar eran los mas acertados ni conocemos procedimientos automaticos para suseleccion. Por este motivo se realizaron distintas pruebas, con diferentes valores e imagenes, ynos quedamos con aquellos valores que presentaban unos mejores resultados.

El parametro U , que aparece en el algoritmo 3 (pagina 24) de esta memoria, es el umbral quese utiliza para determinar cual es la diferencia maxima que pueden presentar dos pixels entresı, para determinar si son parecidos o no, durante el proceso de binarizacion de un determinadonivel de la piramide de imagenes. Su valor es el que se indica en la tabla, simplemente porque secreyo adecuado para obtener el resultado que se pretendıa, ademas de ser un valor con el cuallos resultados eran buenos.

46

8.4. Tiempo de ejecucion

8.4. Tiempo de ejecucion

El tiempo de ejecucion del metodo implementado, desglosado para cada una de las fases yexpresado en milisegundos, es el que se observa en la Tabla 8.2. El tiempo de ejecucion se hadeterminado despues de realizar una media entre 10 ejecuciones distintas del algoritmo, tomandoen cada una de ellas, una de las 10 imagenes que tenıamos donde el codigo aparece sin ninguntipo de mancha. El ordenador con el cual se han realizado cada una de las mediciones es un IntelPentium 4 a 1.70 GHz con 376 MB de RAM.

Como vemos el tiempo que tarda en ejecutarse el programa no es muy elevado, aunque estese verıa incrementado si se aumenta el tamano de la imagen a analizar.

Tabla 8.2.: Tiempo de ejecucion de cada una de las fases

Fase Tiempo (ms)Deteccion de bordes 339Deteccion de regiones candidatas 27Etiquetado y filtrado de regiones 39Estimacion de la orientacion y rectificacion 633Decodificacion 28Tiempo Total 1066

En la etapa de estimacion de la orientacion y rectificacion el tiempo es bastante mas elevadoque en las otras fases, cuando parece que las operaciones que en ella se realizan no deban costartanto. Este aumento en el tiempo es debido a que, para la estimacion de la orientacion, calculamosla mediana de los puntos de borde de la subimagen centrada en el codigo que se obtiene en fasesanteriores, y esta operacion requiere que los valores de los puntos de bordes esten ordenados,utilizando para ello el metodo de la burbuja, que es el causante de este incremento del tiempo.Se utiliza este metodo de ordenacion por simplicidad, sin embargo si quisieramos conseguir unmetodo mas eficiente tendrıamos que implementar otro metodo de ordenacion mas eficiente.

Por ultimo, resenar que el tiempo que emplea el metodo, como hemos comentado, no es muyelevado, incluso sin haber dedicado mucho tiempo a la optimizacion del mismo teniendo encuenta la eficiencia. Con lo cual se puede decir que es un metodo que se presta a ser utilizadoen aplicaciones para decodificacion de codigos de barras, en las que se requiera resultados alinstante.

8.5. Duracion del proyecto

En la siguiente tabla vamos a mostrar el tiempo que hemos empleado en la realizacion denuestro proyecto, tanto en semanas como en horas. Se ha desglosado el mismo en un conjunto deetapas generales que incluye desde la recopilacion inicial de informacion sobre codigos de barrashasta la composicion de esta memoria. Simplemente recalcar que el tiempo que se muestra enestas fases no solo incluye la implementacion del proceso empleado en esa fase, sino tambien eltiempo empleado pensando la idea de como hacerlo, al igual que las posibles modificaciones quese hayan podido realizar de lo que en un principio se tenıa pensado. Con esto queremos recalcarque normalmente se utiliza mas tiempo en pensar como hacer las cosas que en la implementacionde las mismas. Ademas siempre surgen contratiempos que provocan ciertos retrasos que no sehabıan previsto.

47


Tabla 8.3.: Tiempo empleado en la realizacion del proyecto

Etapa Semanas (5 dias) Horas/semanaRecopilacion de informacion 2 40Diseno e implementacion de la localizacion 10 300Diseno e implementacion de la decodificacion 4 120Documentacion y redaccion memoria 4 120Total 20 580

En la tabla el calculo de horas/semana se ha realizado teniendo en cuenta que para la etapade recopilacion de informacion se utilizaron 4 horas/dia y para el resto de etapas 6 horas/dia.

48

9. Conclusiones

El metodo implementado para la decodificacion de codigos de barras podemos concluir quepresenta un buen funcionamiento cuando las imagenes que se analizan no contienen codigos debarras danados o afectados por algun tipo de ruido, como rayas o manchas, pero por el contrariosi los codigos que aparecen en las imagenes si que presentan ruido, el metodo no resulta sersuficientemente robusto. Ademas esta tecnica se ve afectada de manera negativa por la calidadde la imagen, ya que si esta no cumple unas condiciones bastante buenas, el proceso tiendea fallar y por tanto la decodificacion no es posible. La solucion pasarıa seguramente por unpreproceso de la imagen a tratar.

Otra caracterıstica a considerar de este metodo es que realiza los calculos de forma eficiente,aunque este tiempo depende en gran medida del tamano de la imagen. Sin embargo en nuestrocaso, donde se ha utilizado un tamano de imagen fijo, el resultado se obtenıa con bastanterapidez.

En el proceso de la decodificacion, la imagen binaria en la cual nos basamos para posterior-mente interpretar el codigo se obtiene despues de una serie de pasos de la imagen original. Serıaa lo mejor mas conveniente utilizar la imagen de bordes de alguna forma, ya que de esta maneraserıamos capaces de decodificar no solo codigos de barras con espacios blancos y barras negras,sino que podrıamos decodificar codigos donde las barras y espacios fuesen de cualquier color aparte del blanco y negro. Esto es debido a que la obtencion de bordes nos indica los cambios deintensidad que aparecen en la imagen y no depende del color de las barras ni espacios, aunquesuponemos que serıa necesario de igual manera recurrir a la imagen de niveles de gris, pero soloa nivel consultivo sin depender de ella, simplemente para conocer en cada cambio que se producede que nivel venimos y a cual nos dirigimos.

Recalcar que el proceso de localizacion del codigo de barras dentro de la imagen es independi-ente del tipo de codigo de barras, es decir, cualquier codigo de barras cuya simbologıa sea la debarras y espacios puede ser localizado mediante la tecnica de deteccion utilizada en este metodo.Sin embargo, para la fase de decodificacion, sı que se explota el conocimiento previo que se tienedel tipo de codificacion que se utiliza, todo ello con el objetivo de simplificar esta operacion.

Tambien mencionar que serıa interesante realizar pruebas con una baterıa de imagenes muchomayor, para de esta forma mejorar en cuanto a la deteccion y decodificacion de codigos de barrasen imagenes de poca calidad y con ruido, como manchas, rayas, o cualquier otro factor externoque modifique el codigo.

Como posibles extensiones o trabajos futuros cabrıa la posibilidad de intentar que el procesono solo funcionase con codigos de barras EAN-13, sino que valiese para otros muchos tiposde codigos que existen en el mercado actual. Sin embargo hay que tener en cuenta la posibledificultad que ello conlleva, ya que cada codigo utiliza una codificacion distinta y por tanto, queel mismo procedimiento funcionase para una gran variedad de codigos puede ser complicado.Ademas se presenta el problema de, una vez captada la imagen, reconocer que tipo de codigose esta tratando para utilizar en su decodificacion una serie de pasos que podrıan ser diferentessegun el tipo o generalizar el proceso de decodificacion.

49

9. Conclusiones

50

A. Detector de bordes de Canny

Como se ha comentado en esta memoria, se penso en la deteccion de bordes como una posibletecnica para la localizacion del codigo de barras dentro de una imagen, debido a las caracterısticasque este presenta. Por esta razon, se utiliza para tal objetivo, el algoritmo de deteccion de bordesde Canny, ya que este es presentado en la bibliografıa en general como uno de los mejores metodospara la deteccion de bordes y con el cual se obtienen unos buenos resultados.

El algortimo de Canny [24] se fundamenta en la teorıa de operadores primera derivada parala extraccion de bordes y se desglosa en tres grandes pasos:

1. Obtencion del gradiente (magnitud y orientacion del vector gradiente en cadapıxel)

La entrada es una imagen I corrompida por ruido. Sea H un nucleo Gaussiano discretocon media cero y desviacion estandar σ.

Suavizar la imagen I con dicho nucleo para obtener una imagen de salida J .

Para cada pıxel (i, j) en J obtener la magnitud y modulo del gradiente basandose enlas siguientes expresiones:El gradiente de una imagen f(x, y) en un punto (x, y) se define como un vectorbidimensional dado por la ecuacion:

G [f(x, y)] =[

Gx

Gy

]=

[ ∂∂xf(x, y)∂∂yf(x, y)

]siendo un vector perpendicular al borde, donde el vector G apunta en la direccion devariacion maxima de f en el punto (x, y) por unidad de distancia, con la magnitud ydireccion dadas por:

|G| =√

G2x + G2

y,

φ(x, y) = tan−1 Gy

Gx

Es una practica habitual aproximar la magnitud del gradiente con valores absolutosde la siguiente manera:

|G| = |Gx|+ |Gy|

Obtendremos dos imagenes de salida: Em de la magnitud del gradiente y Eo de la ori-entacion, de acuerdo a las expresiones anteriores.

2. Supresion no maxima al resultado del gradiente

Con Em y Eo como entradas y una nueva imagen IN como salida, considerar las cuatrodirecciones d1, d2, d3, d4 identificadas por las orientaciones de 0o, 45o, 90o y 135o conrespecto al eje horizontal. Para cada pıxel (i, j):

Encontrar la direccion dk que mejor se aproxima a la direccion Eo(i, j) (la perpen-dicular al borde).

51

A. Detector de bordes de Canny

Si Em(i, j) es mas pequeno que al menos uno de sus dos vecinos en la direccion dk,al pıxel (i, j) de IN se le asigna el valor 0, IN (i, j) = 0 (supresion), de otro modoIN (i, j) = Em(i, j).

La salida IN (i, j) es una imagen con los bordes adelgazados, es decir, es Em(i, j) despuesde la supresion no maxima de puntos de borde.

3. Histeresis de umbral a la supresion no maxima

La salida IN (i, j) suele contener maximos locales creados por el ruido. Se podrıan elimi-nar los pixels por debajo de un determinado umbral, pero esto presenta problemas. Unasolucion puede ser la histeresis de umbral, cuyo procedimiento es el siguiente:

Tomar como entrada IN , que es la salida del proceso anterior, Eo la orientacion delos puntos de borde de la imagen, y dos umbrales t1 y t2, tales que t1 < t2.

Para todos los puntos de IN y explorando IN en un orden fijo:

• Localizar el siguiente punto de borde no explorado previamente, IN (i, j), tal queIN (i, j) > t2.

• Comenzar a partir de IN (i, j), seguir las cadenas de maximos locales conectadosen ambas direcciones perpendiculares a la normal de borde, siempre que IN > t1.Marcar todos los puntos explorados y salvar la lista de todos los puntos en elentorno conectado encontrado.

La salida es un conjunto de bordes conectados de contornos de la imagen, ası comola magnitud y orientacion, describiendo las propiedades de los puntos de borde.

52

B. Algoritmo clasico de etiquetado decomponentes conexas

Durante una de las fases de nuestro metodo, necesitamos poder elegir de entre un conjunto deregiones aquella que tiene mayor probabilidad de ser la zona donde se encuentra el codigo. Sinembargo, para llegar a este filtrado, previamente necesitamos etiquetar de alguna manera estasregiones, y ası poder distinguir unas de otras. Pero no solo distinguir, sino poder seleccionar laque nosotros queramos. Para esta tarea un algoritmo de etiquetado de componentes conexas sepresentaba como una buen opcion.

El algoritmo clasico de etiquetado de componentes conexas [24] se caracteriza por realizarsolamente dos pasadas a traves de la imagen y necesita mantener durante todo el proceso unatabla de equivalencias de etiquetas.

El primer paso del algoritmo consiste en la propagacion de etiquetas, es decir, como en lamayorıa de algoritmos de este tipo, procesa en cada instante una fila de la imagen y asignanuevas etiquetas al primer pıxel de cada componente, intentando ademas propagar la etiquetade cada pıxel a sus pixels vecinos, que se encuentran a su derecha o por debajo de el.

Cuando se llega a la situacion en la que dos etiquetas distintas se propagan al mismo pıxel,prevalece la mas pequena y cada equivalencia que se encuentra es introducida en una tabla deequivalencias. Cada una de las entradas de la tabla esta formada por un par ordenado, dondelos valores de sus componentes son las etiquetas equivalentes halladas durante el proceso.

Una vez realizado este paso, se calculan las clases de equivalencias tomando el cierre transitivodel conjunto de equivalencias almacenadas en la tabla de equivalencias. A cada una de las clasesde equivalencia encontradas se le asigna una etiqueta, generalmente la mas pequena (o la masantigua de la clase).

En el segundo paso se asigna a cada pıxel la etiqueta de la clase de equivalencia correspondientecalculada en el paso anterior.

El algoritmo clasico de etiquetado de componentes conexas se describe en el Algoritmo 4.La funcion Vecinos() devuelve el conjunto de los vecinos ya etiquetados de un determinadopıxel en su misma lınea o en la lınea previa. La funcion NuevaEtiqueta() genera una nuevaetiqueta con valor entero cada vez que es llamada. La funcion Etiquetas() recibe como entrada unconjunto de pixels ya etiquetados y devuelve el conjunto de sus etiquetas. Por ultimo la funcionClasesEquivalencia() simplemente encuentra las clases de equivalencia de entre el conjunto deequivalencias almacenadas en la tabla correspondiente.

53

B. Algoritmo clasico de etiquetado de componentes conexas

Algoritmo 4 Metodo clasico de etiquetado de componentes conexasEntrada: Una imagen binaria I de tamano M ×NSalida: Una imagen etiquetada E, donde E(i, j) es la etiqueta de I(i, j)1: Inicializar la tabla de equivalencias T2: for i ⇐ 1 to M do3: for j ⇐ 1 to N do4: E(i, j) ⇐ 05: if I(i, j) = 1 then6: V ⇐ Vecinos(i, j)7: if V = ∅ then8: e ⇐ NuevaEtiqueta()9: else

10: e ⇐ mın(Etiquetas(V ))11: E(i, j) ⇐ e12: for all e′ ∈ Etiquetas(V ) ∧ e′ 6= e do13: T ⇐ T ∪ (e′, e)14: C ⇐ ClasesEquivalencia(T )15: for all c ∈ C do16: Equivalente[c] ⇐ mın(Etiquetas(c))17: for i ⇐ 1 to M do18: for j ⇐ 1 to N do19: if I(i, j) = 1 then20: E(i, j) ⇐ Equivalente[Clase(E(i, j)]

54

C. Metodo de Otsu

Con el objetivo de poder calcular de forma automatica un umbral a partir del cual binarizaruna imagen y evitar ası los inconvenientes que presenta la eleccion de un umbral fijo, se penso enla utilizacion del metodo de Otsu como opcion acertada para tal fin.

El metodo de Otsu [8], propuesto en 1979, es un algoritmo para la determinacion automaticade un umbral de binarizacion a partir del histograma de una imagen. Si consideramos que elconjunto de niveles de gris que conforman una imagen son G = {0, 1, 2, . . . , L}, siendo L el valormaximo de niveles de gris, el umbral que vamos a obtener se considera el punto que parte lospixels de una imagen en dos clases de niveles de gris C0 = {0, 1, . . . , t} y C1 = {t+1, t+2, . . . , L},donde t es el umbral optimo que maximiza la separabilidad de estas dos clases.

El metodo esta basado en un analisis discriminante. Un umbral optimo puede ser determinadominimizando algunas de las siguientes funciones con respecto a t:

λ =σ2

B

σ2W

, η =σ2

B

σ2T

, k =σ2

T

σ2W

De los tres criterios a minimizar, el segundo es el mas simple. Por tanto, el umbral optimo sedefine como:

t∗ = arg mınt∈G

η(t)

donde

σ2T =

L∑i=0

(i− µT )2Pi, µT =L∑

i=0

iPi,

σ2B = w0w1(µ1 − µ0)2, w0 =

t∑i=0

Pi, w1 = 1− w0,

µ1 =µT − µt

1− w0, µ0 =

µt

w0

µt =t∑

i=0

iPi, Pi =ni

n

donde ni es el numero de pixels con nivel de gris i y n es el numero total de pixels en la imagendada definido por n =

∑Li=0 ni. Ademas, Pi es la probabilidad de aparicion del nivel de gris i

definido como Pi = nin .

Por ultimo, solo recalcar que la bibliografıa encontrada acerca de este metodo presentabaerratas y finalmente el metodo que aquı se presenta y que es el implementado en la memoria,surge de la combinacion de las distintas fuentes consultadas [10, 8].

55

C. Metodo de Otsu

56

D. Caracterısticas del codigo EAN-13

Existe una gran variedad de codigos de barras en el mercado, sin embargo en nuestro proyectonos hemos dedicado a trabajar con una sola clase de ellos, el codigo EAN-13 [20], uno de losmas famosos y utilizados hoy en dıa.

El sistema de codificacion Universal Product Code (UPC) fue adoptado en los EE.UU. porla industria de la alimentacion en los anos 70. Presentaba una serie de ventajas como eran surapidez, precision y fiabilidad al entrar informacion de stock en las computadoras. Este triunfotan repentino llevo al desarrollo del European Article Numbering System (EAN), una simbologiasimilar a la UPC, que esta ampliamente difundida por Europa y el resto del mundo.

Existen varias versiones de estos codigos, siendo el codigo de barras EAN-13 el mas utilizado.Esta formado por: un margen izquierdo, un dibujo normalizado de separacion, un dibujo que re-presenta directamente seis dıgitos e indirectamente un septimo, un dibujo central de separacion,un dibujo de barras y espacios que representa directamente seis dıgitos, un dibujo normalizadode separacion y un margen derecho. De forma grafica lo podemos observar en la Figura D.1.

Figura D.1.: Formato codigo EAN-13

Cada codigo de barras contiene 13 valores, desde las posiciones 1 a la 13. El significado deestos dıgitos es el que se muestra en la Tabla D.1.

En el codigo de barras existen dos separadores izquierdo y derecho, y una lınea intermediamas larga. Estas tres lineas son mas largas que el resto y son usadas para ((calibrar)) el escaner ala dimension del codigo de barras. El formato de estos separadores se muestra en la Tabla D.2.

La primera posicion cae a la izquierda del borde izquierdo y tiene un significado especial, losotros doce dıgitos estan escritos dentro del codigo y estan divididos en dos grupos por la lıneaintermedia. Cada valor esta codificado a traves de 7 modulos: negro=1 y blanco=0, formandodos parejas de barras de diferentes gruesos. Por tanto, cada dıgito se representa mediante dosbarras y dos espacios que tienen una anchura total de siete unidades o modulos, donde cada

57


Tabla D.1.: Significado de los dıgitos del codigo segun la posicionPosicion Significado1, 2 identificacion del paıs donde se comercializa el producto3 identificacion del paıs (a veces del fabricante)4, 5, 6, 7 identificacion del fabricante del producto8, 9, 10, 11, 12 identificacion del producto13 dıgito de verificacion (su valor es calculado)

Tabla D.2.: Caracterısticas de los separadoresSeparador CaracterısticasIzquierdo 3 modulos (2 barras con 1 espacio al medio, codificado: 101)Derecho 3 modulos (2 barras con 1 espacio al medio, codificado: 101)Central 5 modulos (3 espacios con 2 barras intercaladas, codificado: 01010)

barra y cada espacio pueden tener una anchura de una, dos, tres o cuatro unidades.En la simbologıa EAN pueden elegirse tres formas distintas de codificacion A, B y C para

representar cada dıgito. Estas formas se utilizan para codificar los caracteres numericos ubicadosentre las posiciones 2 y 13.

Para representar la primera mitad del codigo de barras se emplea una combinacion de losconjuntos numericos A y B, donde el orden de los conjuntos numericos utilizados representa asu vez un septimo dıgito, que aparece al principio de la secuencia de caracteres situada debajodel codigo de barras. El conjunto numerico C se emplea solo para la segunda mitad del codigode barras, lo que provoca que el dispositivo lector pueda leer el codigo en cualquier sentido ydecodificarlo correctamente.

Por tanto los caracteres del tipo A y B estaran a la izquierda del separador central, mientrasque los del tipo C se ubican a la derecha del separador central, como se puede observar en laFigura D.2.

Figura D.2.: Tipo de codificacion segun la posicion

La codificacion para cada uno de los tres diferentes posibilidades se muestran en la Tabla D.3,teniendo en cuenta que 1=negro y 0=blanco.

Las secuencias A y B de los caracteres ubicados en las posiciones de la 2 a la 7, determinanel caracter numerico ubicado en la posicion 1. Este caracter no esta representado por barras niespacios y generalmente se imprime en la zona de la izquierda. En este punto hemos encontrado

58

Tabla D.3.: Representacion de cada dıgito segun el tipo de codificacionDıgito Codificacion A Codificacion B Codificacion C

(Parte izquierda) (Parte izquierda) (Parte derecha)0 0001101 0100111 11100101 0011001 0110011 11001102 0010011 0011011 11011003 0111101 0100001 10000104 0100011 0011101 10111005 0110001 0111001 10011106 0101111 0000101 10100007 0111011 0010001 10001008 0110111 0001001 10010009 0001011 0010111 1110100

una cierta controversia en cuanto a que, segun la fuente consultada, el caracter numerico de laposicion 1 depende de la combinacion de los caracteres de la primera parte del codigo teniendoen cuenta el tipo de codificacion como hemos comentado o por el contrario, es el primer caracterel que determina la combinacion para cada uno de los seis primeros dıgitos. Aunque por logicaparece mas probable la primera opcion, ya que el primer dıgito no se encuentra codificadodentro del codigo y por tanto los lectores no pueden saber de que dıgito se trata. Las posiblescombinaciones que determinan el valor del primer dıgito son las que se muestran en la Tabla D.4.

Tabla D.4.: Posibles combinaciones de los seis primeros dıgitos del codigoPosicion 1 Posicion 2 Posicion 3 Posicion 4 Posicion 5 Posicion 6 Primer dıgito

A A A A A A 0A A B A B B 1A A B B A B 2A A B B B A 3A B A A B B 4A B B A A B 5A B B B A A 6A B A B A B 7A B A B B A 8A B B A B A 9

Por ultimo, el dıgito de verificacion se calcula siguiendo este procedimiento:

1. Multiplicar el valor de cada caracter en posicion par por 3.

2. Sumar entre sı los 6 productos anteriores, cada uno de valor entre 0 y 27, mas los valoresde cada caracter en posicion impar, excepto la posicion 13, obteniendo ası un valor que sellama ((Suma de Productos)) (SP ).

3. Dividir la suma de productos por 10 (constante), obteniendo un cociente (C) y un resto(R), o sea C = [SP

10 ] y R = SP − 10C.

4. Restarle a 10 el resto, obteniendo el valor del caracter de verificacion (CV ) que se ubicara enla posicion 13 del codigo, es decir, CV = 10−R.

59


La autoverificacion del caracter (CV ) recien calculado se realiza con el valor de la posicion13. Si el valor obtenido coincide con el de la posicion 13, queda confirmado y verificado.

60

Bibliografıa

[1] Aplicacion para manejo y visualizacion de imagenes. http://www.tele.ucl.ac.be/PEOPLE/DOUXCHAMPS/ieee1394/coriander. Ultimo acceso: Junio 2005.

[2] History of barcodes. http://www.basics.ie/History.htm. Ultimo acceso: Junio 2005.

[3] Informacion general sobre codigos de barras. http://www.serebella.com/encyclopedia/article-Barcode.html. Ultimo acceso: Junio 2005.

[4] Informacion general sobre impresoras de codigos de barras. http://www.dimension-x.com/cf-onsprn2.htm. Ultimo acceso: Junio 2005.

[5] Kjersti Aas and Line Eikvil. Decoding bar codes from human-readable characters. PatternRecognitions Letters (PRL), 18:1519–1527, 1997.

[6] Russ Adams. Informacion general sobre codigos de barras. http://www.barcode-1.com.Ultimo acceso: Junio 2005.

[7] Jorge Badenas Carpio, Jose Luis Llopis Borras, and Oscar Coltell Simon. Curso practicode programacion en C y C++. Publicacions de la Universitat Jaume I, 1997.

[8] M. Cheriet, J.N. Said, and C. Y. Suen. A recursive thresholding techniques for imagesegmentation. IEEE Transactions on Image Processing, 7:918–921, 1998.

[9] Secretarıa de Estado de Cultura. Manual del Usuario, 2.a edicion espanola, 2001. Traduccionde ISBN User’s Manual, 4th ed.

[10] Arturo de la Escalera Hueso. Vision por computador: fundamentos y metodos. PrenticeHall, 2001.

[11] Øivind Due Trier and Anil K. Jain. Goal-directed evaluation of binarization methods. IEEETransactions on Pattern Analysis and Machine Intelligence, 17:1191–1201, 1995.

[12] Nick Efford. Digital Image Processing. A Practical Introduction Using Java. Addison-Wesley, 2000.

[13] H. Freeman and R. Shapira. Determining the minimum-area encasing rectangle for anarbitrary closed curve. Communications of the ACM, 18:409–413, 1975.

[14] Francisco Ortegon Gallego. LATEX, primeros pasos. MASSON, S.A., 1992.

[15] C. Godin and P. Lockwood. DTW schemes for continuous speech recognition: a unifiedview. Computer Speech and Language, 3:169–198, 1989.

[16] Silicon Graphics. Standard Template Library Programmer’s Guide. http://www.sgi.com/tech/stl. Ultimo acceso: Junio 2005.

61

Bibliografıa

[17] The MathWorks Inc. Image Acquisition Toolbox User’s Guide. For Use with MATLAB.2003–2005.

[18] Eugene Joseph and Theo Pavlidis. Bar code waveform recognition using peak locations.IEEE Transactions on Pattern Analysis and Machine Intelligence, 16:630–640, 1994.

[19] Joseph Kittler, Mohamad Hatef, Robert P.W. Duin, and Jiri Matas. On combining classi-fiers. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20:226–239, 1998.

[20] Vault Information Services LLC. EAN-13 Symbology. http://www.barcodeisland.com/ean13.phtml. Ultimo acceso: Junio 2005.

[21] Antonio M. Lopez, Felipe Lumbreras, Joan Serrat, and Juan J. Villanueva. Evaluationof methods for ridge and valley detection. IEEE Transactions on Pattern Analysis andMachine Intelligence, 21:327–335, 1999.

[22] Ruben Muniz, Luis Junco, and Adolfo Otero. A robust software barcode reader usingthe Hough transform. IEEE International Conference on Information, Intelligence, andSystems, pages 313–319, 1999.

[23] Hermann Ney. The use of a one-stage dynamic programming algorithm for connected wordrecognition. IEEE Trans. on ASSP, 32:263–271, 1984.

[24] Gonzalo Pajares and Jesus M. de la Cruz. Vision por Computador. Imagenes digitales yaplicaciones. Ra-Ma, 2001.

[25] L.R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recog-nition. Proceedings of the IEEE, 77:257–286, 1989. http://www.ai.mit.edu/courses/6.867-f02/papers/rabiner.pdf.

[26] Jun Rekimoto, Yuji Ayatsuka, and Kazuteru Hayashi. Augment-able reality: Situated com-munication through physical and digital spaces. International Symposium on WearableComputers (ISWC), pages 68–75, 1998.

[27] Stephen Shellhammer, David P. Goren, and Theo Pavlidis. Novel signal-processing tech-niques in barcode scanning. IEEE Robotics & Automation Magazine, 6:57–65, 1999.

[28] Peter Sundstrom. Bar code reader for surface mounting systems. http://www.f.kth.se/~f96-psu/thesis.html, 2001. Master thesis on KTH - Kungliga Tekniska Hogskolan[Royal Institute of Technology] (Stockholm).

[29] David Tschumperle. The C++ template image processing library. http://cimg.sourceforge.net. Ultimo acceso: Junio 2005.

[30] Todd Wittman. Deblurring and restoration in barcode signal processing. SIAM (Societyfor Industrial and Applied Mathematics) News, 37, 2004.

[31] William J. Wolfe, Jim Gunderson, and Matthew E. Walworth. Computer vision barrelinspection. Mobile Robots VIII, 2058:128–133, 1993.

62

Localización y decodificación de códigos de barras en imágenes digitales

Education

Transcript of Localización y decodificación de códigos de barras en imágenes digitales