BRPI0708452A2 - método e aparelho de correção de distorção baseado em modelo - Google Patents

Abstract

MéTODO E APARELHO DE CORREçãO DE DISTORçãO BASEADO EM MODELO. A invenção refere-se a um aparelho e método para processar uma imagem capturada e, mais especificamente, para processar uma imagem capturada que compreende um documento. Em uma modalidade, um aparelho compreende uma câmera para capturar os documentos está descrito. Em outra modalidade, um método para processar uma imagem capturada que inclui um documento compreende as etapas de distinguir um documento de imagem formada de seu fundo, ajustar a imagem capturada para reduzir as distorções criadas pela utilização de uma câmera e orientar apropriadamente o documento.

Description

Relatório Descritivo da Patente de Invenção para "MÉTODO EAPARELHO DE CORREÇÃO DE DISTORÇÃO BASEADO EM MODELO".

A presente invenção refere-se a este pedido é uma continuaçãoem parte do Pedido U.S. Número de Série 11/368.260 depositado em 02 deMarço de 2006. Este pedido reivindica o benefício do Pedido U.S. Númerode Série 11/368.260 depositado em 02 de Março de 2006, cujas descriçõesestão aqui incorporadas por referência.

CAMPO DA INVENÇÃO

Um aparelho e método para processar uma imagem capturadae, mais especificamente, para processar uma imagem capturada que com-preende um documento.

ANTECEDENTES DA INVENÇÃO

Cada vez mais documentos são armazenados em formato deimagem, ou pixel, ao invés de código ASCII já que as mídias de armazena-mento, tal como o CD-ROM, estão tornando-se menos dispendiosas. Estesdocumentos de imagem formada são capazes de serem utilizados para refe-rência, pesquisa, ou distribuição. A imagem armazenada dos documentos éusualmente capturada por um dispositivo de entrada tal como um scanner ouuma câmera digital. No entanto, a distorção de imagem é um problemaquando o conteúdo de documento na imagem é capturado por um scannerou, ainda pior, por uma câmera digital.

A Figura 1A é um diagrama de blocos que apresenta os compo-nentes típicos de um scanner. Um scanner é tipicamente utilizado para cap-turar uma imagem de um documento 110. Um documento 110 é colocadosobre a placa de scanner 112. Um cabeçote de escaneamento 120, o qual égeralmente compreendido de um subsistema ótimo 122 e um dispositivo a-coplado em carga ("CCD") 124, é movido através do documento 110. Apesarda Figura 1A apresentar somente uma vista bidimensional, o cabeçote deescaneamento 120 pode mover-se através do documento tanto na direçãoilustrada pela seta 114 quanto em uma direção ortogonal à seta 114. O sub-sistema ótico 122 focaliza a luz refletida do documento 110 por sobre umCCD 124. O CCD 124 está freqüentemente implementado como uma redebidimensional de elementos capacitivos fotossensíveis. Quando a luz é inci-dente sobre os elementos fotossensíveis do CCD 124, uma carga é aprisio-nada em uma região de esgotamento dos elementos de semicondutor. Aquantidade de carga associada com os elementos capacitivos fotossensíveisestá relacionada com a intensidade de luz incidente sobre os respectivoselementos recebida durante um período de amostragem. Conseqüentemen-te, a imagem é capturada pela determinação da intensidade de luz incidentenos respectivos elementos capacitivos fotossensíveis através da amostra-gem dos elementos. As informações analógica produzidas pelos elementoscapacitivos fotossensíveis são convertidas para informações digitais por umconversor analógico para digital (A/D) 130. Um conversor A/D 130 pode con-verter as informações analógicas recebidas do CCD 124 em um modo ouserial ou paralelo. As informações digitais convertidas podem ser armazena-das na memória 140. As informações digitais são então processadas por umprocessador 150 de acordo com um software de controle armazenado naROM 180. O usuário pode controlar os parâmetros de escaneamento atra-vés de uma interface do usuário 170 e a imagem escaneada é emitida atra-vés de uma porta de saída 160.

Um diagrama de blocos de uma câmera digital está apresentadona Figura 1B. Um subsistema ótico 122 de uma câmera digital pode ser utili-zado para focalizar a luz refletida de um documento 110 por sobre um CCD124, tal como no scanner. Em outras câmeras digitais, outros dispositivos doque um CCD são utilizados para capturar a luz refletida da imagem, tais co-mo os sensores de CMOS. No contexto de uma câmera digital, em oposiçãoa um scanner, o subsistema ótico 122 não é movido ao longo da superfíciedo documento, como em um scanner. Ao contrário, em uma câmera digital, osistema ótico 122 está geralmente estacionário em relação ao objeto, talcomo um documento, a ter a imagem formada. Além de câmeras digitais, asfotografias capturadas de câmeras baseadas em filme podem também serdigitalizadas.

As câmeras oferecem vantagens significativas em relação aosscanners para capturar as imagens de documentos e outras imagens. Porexemplo, as câmeras são geralmente mais portáteis do que os scanners.

Além disso, como os scanners requerem que uma imagem capturada sejacolocada sobre a placa de scanner, as câmeras são capazes de capturaruma rede de imagens mais ampla do que os scanners. No entanto, a utiliza-ção de câmeras cria dificuldades na captura de imagens que não existemquando utilizando um scanner. Por exemplo, as condições de luz variamquando utilizando uma câmera, enquanto que as condições de luz são ge-ralmente controladas em scanners. Além disso, a utilização de uma câmeraintroduz distorções de imagem, as quais podem depender de várias variá-veis, tais como o ângulo da câmara em relação à imagem, a lente utilizadapela câmera e a sua distância da imagem, se a imagem que inclui um docu-mento está situada sobre uma superfície plana ou curva, e outros fatores.

Como o scanner utiliza um cabeçote de scanner móvel, a uma distância fixade um documento a ter a imagem formada, estas distorções geralmente nãoocorrem nos scanners.

Muita pesquisa tem sido feita para resolver o problema de dis-torção de imagem. Brown e Seales propuseram um algoritmo de correção dedesalinhamento geral para os documentos arbitrariamente distorcidos combase em imagens 3D. ("Image Restoration Arbitrarily Warped Documents",IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, N210, (2004)). Zhang, et al. desenvolveu um algoritmo de profundidade desombra para processar as imagens de documento capturadas por um scan-ner de leito plano. ("Restoration of Curved Document Images Through 3DShape Modeling", Proc. of the 6th International Conference on Document A-nalysis and Recognition, pp. 10-15 (2004). Mas esta técnica é altamente de-pendente da condição de iluminação e, portanto, não é adequada para asimagens capturadas com uma câmera digital.

Reconhecendo que as câmeras digitais são dispositivos de en-trada mais convenientes comparados com os scanners, os pesquisadoresdesenvolveram modelos para reduzir os problemas de distorção de imagemem imagens capturadas por câmeras digitais. Por exemplo, Cao, et al. de-senvolveram um modelo paramétrico para estimar a forma de cilindro de umlivro aberto. ("Rectifying the Bound Document Image Captured by the Came-ra: A Model Based Approach", Proc. of the International Conference on Do-cument Analysis and Recognition, pp. 71-75 (2003)). Uma limitação principalda utilização desta técnica é que o modelo somente funciona quando o planode lente da lente de câmera é paralelo à superfície do livro de imagem for-mada. Liang, et al. desenvolveram uma superfície desenvolvível para mode-lar a superfície de página de um livro e explorar as propriedades (paralelis-mo e espaçamento de linhas igual) do conteúdo textual impresso sobre apágina para recuperar a forma de superfície. ("Flattening Curved Documentsin Imagès", International Conference on Computer Vision and Pattern Re-cognition, pp. 338-345 (Junho de 2005)). Pela utilização desta técnica, o pla-no de lente da lente de câmera não é mais requerido ser paralelo à superfí-cie de um livro. No entanto, os modelos utilizados tanto por Cao quanto porLiang para corrigir a distorção sobre um documento com imagem formadaestão baseados em informações de linha de texto. Em outras palavras, estesmodelos são altamente dependentes da existência de linhas de texto no livrode imagem formada. Se uma página de um livro tiver muitas imagens ou e-quações ao invés de linhas de texto, os modelos de Cao e de Liang não fun-cionarão bem.

Portanto, uma necessidade continua a existir para um aparelho emétodo aperfeiçoado para capturar as imagens de documentos que possamutilizar as vantagens das câmeras em relação aos scanners, e no entantoreduza a distorção tipicamente apresentada pela captura de imagens de do-cumentos através de uma câmera em oposição a um scanner. De preferên-cia, o aparelho e método deve ser capaz de reduzir a distorção em uma i-magem capturada independentemente se linhas de texto estão presentessobre o documento com imagem formada, por meio disto permitindo a corre-ção de distorção em uma imagem de documento capturada com figuras eequações. Além disso, o aparelho e método de preferência não deve estarrestrito a imagens que são geradas quando o plano de lente de uma lente decâmera está paralelo com a superfície de um livro.

BREVE SUMÁRIOUm aparelho e método para processar uma imagem capturadaque compreende um documento de imagem formada estão descritos. Emuma modalidade, o aparelho compreende uma câmera estacionária, a qual éutilizada para capturar o documento de imagem formada. Em outra modali-dade, uma câmera não estacionária é utilizada para capturar os documentosde imagem formada. Em ainda outra modalidade, um método para processaruma imagem capturada que inclui um documento compreende as etapas dedistinguir o documento de imagem formada de seu fundo, ajustar a imagemcapturada para reduzir as distorções criadas pela utilização de uma câmerae orientar apropriadamente o documento. Em ainda uma modalidade adicio-nal, um aparelho e método para a correção de distorção de uma imagemcapturada de um documento curvo estão providos.

BREVE DESCRIÇÃO DOS DESENHOS

Figura 1A apresenta um scanner de documentos da técnica an-terior.

Figura 1B apresenta uma câmera digital da técnica anterior.

Figura 2 apresenta um fluxograma geral de um método preferidopara processar uma imagem capturada.

Figura 3 apresenta um fluxograma de outra modalidade de ummétodo para processar uma imagem capturada.

Figura 4 apresenta um fluxograma de um método para executaruma segmentação de acordo com uma das implementações do método deformação de imagem de um documento aqui descrito.

Figura 5 apresenta um fluxograma de um método para executara etapa de consenso de amostra randômica na Figura 4.

Figura 6 apresenta um fluxograma de um método para executara etapa de remoção de valor discrepante ilustrada na Figura 4.

Figura 7 apresenta um fluxograma de outro método para execu-tar uma segmentação de acordo com o método de formação de imagem deum documento aqui descrito.

Figura 8 apresenta um fluxograma de um método para executaras etapas de remoção de distorção ilustradas na Figura 2 e na Figura 3.Figura 9 apresenta um fluxograma de um método para executaras linhas de etapa de texto ilustrada na Figura 3.

Figura 10 apresenta um fluxograma de um método para deter-minar se um documento está apropriadamente orientado em um modo a-prumado de acordo com uma implementação do método de formação deimagem de um documento aqui descrito.

Figura 11 apresenta uma modalidade de um aparelho para cap-turar e processar uma imagem que inclui um documento de imagem formada.

Figura 12 apresenta um fluxograma de um método para deter-minar se um documento está orientado em um modo aprumado de acordocom uma implementação do método de formação de imagem de um docu-mento aqui descrito.

Figura 13 apresenta uma modalidade de um sistema para pro-cessar uma imagem capturada.

Figura 14 apresenta um fluxograma de um método para executaruma correção de distorção de acordo com a presente invenção.

Figura 15 apresenta um fluxograma de um método para geraruma rede de coordenadas curvas para uma imagem de um documento dis-torcido.

Figura 16 apresenta um fluxograma de um método para executara etapa de melhoramento de direção local ilustrado na Figura 15.

Figura 17 apresenta uma imagem original segmentada a ser cor-rigida pela técnica de correção de distorção da Figura 14 e ilustra um méto-do alternativo para aplicar uma rede de coordenadas curvas para uma ima-gem de um documento distorcido.

Figura 18 apresenta um exemplo de uma imagem de uma pági-na de documento distorcida com uma rede de coordenadas curvas.

Figura 19 apresenta uma imagem de um documento com umarede retangular não proporcional, estirada, após a etapa de estiramento daFigura 14.

Figura 20 apresenta um diagrama de projeção em 3D para ilus-trar o modelo utilizado em uma modalidade preferida da presente invençãopara executar a etapa de estiramento da Figura 14.

Figura 21 apresenta uma rede retangular que após a etapa deajuste da Figura 14.

Figura 22 apresenta um diagrama de projeção pata ilustrar adi-cionalmente um modelo preferido para executar a etapa de estiramento daFigura 14.

Figura 23 apresenta uma vista lateral de um livro aberto parailustrar um modelo preferido para executar a etapa de ajuste da Figura 14.

Figura 24 apresenta um diagrama de projeção para ilustrar adi-cionalmente um método para executar a etapa de ajuste da Figura 14.

Figura 25 apresenta uma imagem em miniatura para ilustrar adi-cionalmente um método para executar a etapa de segmentação de área detexto.

Figura 26A apresenta um pequeno segmento de imagem de tex-to para ilustrar adicionalmente um método para executar a etapa de detec-ção de distância de linha de texto da Figura 16.

Figura 26B apresenta uma imagem em miniatura para ilustraradicionalmente um método para executar a etapa de detecção de distânciade linha de texto da Figura 16.

Figuras 27A-F apresentam seis gabaritos direcionais de 9x9 quepodem ser utilizados na execução da etapa de computar e melhorar a matrizde direção da Figura 16.

Figura 28A apresenta uma imagem capturada de um documentoque inclui linhas de texto utilizada para ilustrar adicionalmente um métodopara executar a etapa de melhoramento baseado em matriz de direção daFigura 16.

Figura 28B apresenta uma imagem de um esqueleto de linhasde texto que pode ser gerado das linhas de texto na imagem da Figura 28Aapós a etapa de melhoramento baseado em matriz de direção da Figura 16.

Figura 29A apresenta uma imagem de esqueletos de linhas detexto utilizados para ilustrar adicionalmente um método para executar a eta-pa de extração de linha de texto da Figura 15.

Figura 29B apresenta um exemplo de um esqueleto de linhas detexto afinadas que pode ser gerado da imagem na Figura 29A durante ummétodo da etapa de extração de linha de texto da Figura 15.

Figura 30 apresenta uma banda de detecção vertical que podeser utilizada durante um método para extrair as linhas de texto da imagemda Figura 29B durante a etapa de extração de linha de texto da Figura 15.

Figuras 31A-B apresentam imagens de linha de texto para ilus-trar adicionalmente outro método para executar a etapa de extração de linhade texto da Figura 15.

Figura 32 apresenta um exemplo de uma imagem extraída daimagem segmentada da Figura 17 para utilização em uma técnica de corre-ção de distorção de imagem de acordo com a Figura 14.

Figura 33 apresenta uma imagem de linhas de borda extraídasgeradas da imagem da Figura 32 para utilização em uma técnica de corre-ção de distorção de imagem da Figura 14.

DESCRIÇÃO DETALHADA DE MODALIDADES PREFERIDAS

As modalidades aqui descritas são operáveis para processaruma imagem capturada de uma câmera que compreende um documento. Asmodalidades aqui descritas são operáveis para identificar a imagem de do-cumento capturada de seu fundo. Após a imagem de documento capturadaser isolada de seu fundo, as modalidades aqui descritas são operáveis parareduzir ou remover as distorções da imagem de documento capturada. Asmodalidades aqui descritas são também operáveis para girar a imagem dedocumento capturada para a sua orientação apropriada. Além disso, as mo-dalidades aqui descritas provêem o usuário com uma avaliação do sucessode implementar cada uma das etapas em suas várias modalidades.

A Figura 2 apresenta um fluxograma geral de um método prefe-rido para processar uma imagem digital capturada.Após o início 210, umaimagem digital é recebida na etapa 220. A imagem recebida na etapa 220compreende uma imagem de documento. A imagem digital pode ser recebi-da de várias fontes. Por exemplo, em uma modalidade, a imagem pode serrecebida de uma câmera digital. Em outra modalidade, a imagem pode serrecebida de uma unidade estacionária que compreende uma câmera digital.Em ainda outra modalidade, a imagem pode ser recebida de uma fotografiade filme que foi digitalizada. Em situações onde a imagem foi previamentecapturada por um dispositivo de formação de imagem eletrônico, a imagempode também ser recebida de qualquer um dos meios de armazenamento dearquivos eletrônicos conhecidos.

A etapa 230 opera para identificar a imagem de documento cap-turada do restante da imagem, ou do fundo. A etapa 230 é referida comosegmentação. Esta etapa 230 pode operar para detectar as bordas da ima-gem de documento capturada. Esta etapa 230 pode também operar pararecortar o fundo da imagem da imagem de documento capturada de modo aseparar o documento de seu fundo. A etapa 240, referida como remoção dedistorção, opera para reduzir ou remover as distorções da imagem de docu-,mento capturada. Algumas das distorções as quais a etapa 240 pode operarpara corrigir são as distorções de perspectiva, as distorções de lente, osempenos e as distorções de luz. Outras distorções podem também ser corri-gidas nesta etapa 240. A etapa 250 opera para corrigir a orientação do do-cumento. Esta etapa 250 pode operar para determinar se a imagem de do-cumento capturada deve estar em orientação de retrato ou de paisagem egirar a imagem de documento capturada conseqüentemente. Esta etapa 250também opera para determinar se a imagem de documento capturada estáde cabeça para baixo e girar a imagem de documento capturada conseqüen-temente. Na etapa 260 a imagem de documento processada é emitida. Aimagem de documento processada pode ser emitida 260 através de váriosmeios, tais como exibir uma imagem da imagem de documento processadaem um monitor, salvar a imagem de documento processada em um arquivode computador, transmitir eletronicamente a imagem de documento, ou im-primir a imagem de documento processada.

Em algumas modalidades pode ser desejável executar menosdas etapas refletidas na Figura 2 ou inverter a ordem de certas etapas. Porexemplo, algumas modalidades podem somente incluir a remoção de distor-ção, ou a segmentação e a remoção de distorção. Em outras implementa-ções, pode ser desejável executar somente as etapas de remoção de distor-ção e de orientação.

A Figura 3 apresenta um fluxograma 300 de outra modalidadede um método para processar uma imagem de capturada. Após o início 305,a imagem é recebida na etapa 310. Na etapa 315 a imagem recebida é con-vertida em um mapa de bits independente de dispositivo. Na etapa 320, asegmentação é executada utilizando um processo de segmentação baseadoem borda. O processo de segmentação baseado em borda 320 identifica asbordas do imagem de documento capturada para distinguir a imagem dedocumento capturada de seu fundo.

A Figura 4 apresenta um fluxograma de uma modalidade de umprocesso de segmentação baseado em borda 320. Nesta modalidade, pon-tos de borda horizontais e verticais são localizados. Isto é feito procurandopor pontos de borda. Os pontos de borda são determinados pela identifica-ção de porções da imagem recebida que contém uma transição da porçãode fundo da imagem recebida para a porção de documento da imagem re-cebida. Em uma modalidade, a imagem recebida é escaneada começandodo centro da imagem recebida 410 e também escaneada começando dasbordas da imagem recebida 420. Em uma modalidade, é assumido que aimagem de documento ocupa o centro da imagem recebida. Em outra moda-lidade, é assumido que a porção não de texto da imagem de documentocapturada tem uma intensidade de pixels maior do que o seu fundo. No es-caneamento começando do centro da imagem recebida 410, após encontrara área que pode ser identificada como os pixels de documento, a transiçãopara os pixels de fundo é procurada ao longo do escaneamento. No escane-amento que começa da borda da imagem recebida 420, uma área é identifi-cada como os pixels de fundo ou a transição para os pixels de imagem dedocumento são identificados. O processo pode ser executado utilizando umou ambos estes escaneamentos 410, 420. Em uma modalidade, a imagemrecebida é escaneada 410, 420 tanto na direção horizontal quanto na vertical.Uma etapa de consenso de amostra randômica 430 é então e-xecutada. A Figura 5 apresenta uma modalidade da etapa de consenso deamostra randômica. Nesta modalidade, o consenso de amostra randômica430 é executado selecionando dois pontos randomicamente 510 dos pontosde borda selecionados na etapa 410 e 420. A linha que conecta estes doispontos randomicamente selecionados é então calculada 520. Em uma mo-dalidade, coordenadas de ângulo - distância são utilizadas, onde o valor deângulo corresponde ao ângulo do segmento de linha ao redor do centro daimagem recebida e o valor de distância corresponde à distância do centro daimagem recebida até o ponto mais próximo no segmento de linha. Em outrasmodalidades, outros sistemas de coordenadas podem ser utilizados, incluin-do, por exemplo, as coordenadas Cartesianas ou as coordenadas polares.Estes valores são então armazenados. O processo de selecionar dois pon-tos randômicos dos pontos de borda obtidos em 410 e 420 é repetido paraobter um grupo de amostras 530 suficiente. Em uma modalidade, este pro-cesso é repetido cinco mil vezes, apesar de diferentes tamanhos de amos-tras poderem ser utilizados. Após a amostragem, os pares de pontos queficam todos sobre a mesma linha são agrupados em recipientes. Se os pon-tos de borda iniciais selecionados em 410 e 420 representarem precisamen-te as bordas do documento na imagem recebida, aproximadamente umquarto dos pontos estará distribuído em quatro pequenas faixas que corres-pondem às quatro bordas de documento, enquanto que os pontos restantesestarão dispersos geralmente uniformemente sobre o restante das coorde-nadas possíveis. Os quatro conjuntos de segmentos de linha agrupados quetêm os segmentos de linha mais agrupados 540 e atendem a um limite mí-nimo de segmentos de linha agrupados são identificados como representan-do as quatro bordas do documento na imagem recebida 550. Em uma moda-lidade, esta coleção de segmentos de linha é então determinada ser as bor-das esquerda, direita, superior e inferior de acordo com as suas posiçõesrelativas na imagem recebida.

Após o consenso de amostra randômica 430 ser executado, emuma modalidade, uma etapa de remoção de valor discrepante 440 é execu-tada entre a coleção de pontos de borda para refinar adicionalmente a identi-ficação das bordas de documento. Em uma modalidade, apresentada naFigura 6, isto é executado pela condução de uma regressão linear entre acoleção de pontos de borda que correspondem a uma das bordas da ima-gem de documento recebida. Em uma técnica de regressão linear, uma linhaé traçada tentando conectar mais precisamente a coleção de pontos de bor-da 610. Se o ponto mais distante desta linha de regressão linear for determi-nado estar a uma distância suficientemente distante da linha de regressãolinear 620, o ponto é removido 630 e uma nova regressão linear é executa-da. Este processo é repetido até que o ponto mais distante da linha de re-gressão linear esteja dentro de um valor limite e a linha de regressão linearresultante é determinada ser a linha de borda. Isto é executado sobre cadauma das quatro coleções de pontos de borda que representam as quatrobordas do documento de imagem recebida.

Referindo de volta à Figura 3, na etapa 325, um cálculo da pre-cisão da identificação das linhas de borda da segmentação baseada emborda 320 é determinado. Esta etapa 325 pode ser referida como o cálculoda confiança. Em uma modalidade, a confiança é calculada para cada bordada imagem de documento recebida e o valor mais baixo é determinado ser aconfiança total. Em outra modalidade, o valor de confiança mais alto entre aslinhas de borda é determinado ser a confiança total. Em ainda outra modali-dade, uma combinação da confiança das linhas de borda é utilizada, tal co-mo por exemplo uma média da confiança para as linhas de borda, para de-terminar a confiança total. Uma modalidade para calcular a confiança da de-terminação de uma borda de linha específica é calcular a razão entre o nú-mero de pontos de pixels restantes na coleção daquela borda após a remo-ção de valor discrepante 440 e o número total de pontos de pixels que pode-riam ser encontrados sobre aquela borda. A determinação de confiança po-de ser utilizada para aperfeiçoar a remoção de distorção 240, 350 da ima-gem de documento recebida e pode também ser utilizada para informar a umusuário sobre a precisão de desempenho do sistema para uma imagem re-cebida específica.Em uma modalidade, se as bordas de um documento e o textona imagem não puderem ser encontrados, o processador está programadopara assumir que a imagem é uma imagem não de documento e deixa-ainalterada. O benefício de utilizar esta modalidade é a capacidade de detec-tar quando não existe nenhum documento na imagem provida. Isto é útilporque esta modalidade pode ser utilizada para processar uma série de i-magens que contêm uma mistura de imagens de documentos e o tipo deimagens para as quais as pessoas de outro modo utilizam suas câmerasdiariamente, tais como imagens de pessoas ou cenários. A detecção da au-sência de um documento significa que estas imagens não serão distorcidas.

Na etapa 330, se a confiança na etapa de segmentação baseada em borda320 não for suficientemente alta, então uma segmentação baseada em con-teúdo da etapa 335 pode também ser executada. Alternativamente, a seg-mentação baseada em conteúdo pode ser o único tipo de segmentação exe-cutado.

A etapa de segmentação baseada em conteúdo 335 utiliza o tex-to do documento de imagem capturada para calcular a borda do documentode imagem capturada em relação ao texto. Uma modalidade de um processode segmentação baseado em conteúdo está apresentada na Figura 7. Noprocesso de segmentação baseado em conteúdo da Figura 7, a segmenta-ção é executada pela identificação de componentes conectados na imagemde documento recebida 710 e encontrando o vizinho mais próximo destescomponentes 720. Um componente conectado refere-se a um conjunto depixels na imagem onde cada pixel é preto ou escuro e cada um está adja-cente a pelo menos um outro pixel no conjunto. Os centros dos componen-tes conectados são então conectados em linhas 730, as quais são entãoutilizadas para determinar a borda do texto 740. Destas bordas, uma mar-gem é adicionada 750 de modo a identificar a localização da borda da ima-gem de documento recebida. Apesar do tamanho da borda poder variar, emuma modalidade, uma margem padrão é adicionada na etapa 750.

Referindo de volta à Figura 3, na etapa 340 os cantos da ima-gem de documento capturada são calculados. Em uma modalidade, os can-tos podem ser calculados da interseção das linhas de borda.

Como anteriormente descrito, as etapas de remoção de distor-ção 240, 350 podem envolver uma variedade de ajustes na imagem recebi-da. Em uma modalidade, as etapas de remoção de distorção 240, 350 ajus-tarão a imagem de documento recebida para corrigir as distorções de pers-pectiva na imagem recebida. Por exemplo, em situações onde a imagem nãoé feita a um ângulo diretamente acima e centrado sobre o documento, existi-rá uma distorção de perspectiva da imagem de documento recebida.

Uma modalidade para ajustar a imagem para corrigir a distorçãode perspectiva está apresentada na Figura 8. Esta modalidade envolve ma-pear um conjunto de coordenadas de imagem 810, por exemplo (x, y), paraum novo conjunto de coordenadas de imagem, por exemplo (u, v). Após aetapa de segmentação 230, 320, 335, os quatro cantos do documento sãodeterminados 340. Tipicamente, em um documento que contém distorção deperspectiva, estes quatro cantos corresponderão a um trapezóide, enquantoque um documento deveria geralmente ter a forma de um retângulo. Assim,em uma modalidade, o mapeamento 810 é executado entre o trapezóiderecebido para o retângulo desejado. Uma modalidade para executar estemapeamento 810 é utilizar uma transformação homogênea entre as coorde-nadas de pixels não distorcidos e as coordenadas de pixels distorcidos atra-vés de uma matriz homogênea que representa a transformação da coorde-nada de pixels distorcidos para a coordenada de pixels não distorcidos, oque é conhecido na técnica. A transformação pode ser calculada comparan-do os quatro cantos determinados durante a segmentação 230, 320, 335com dimensões corrigidas da imagem de documento recebida não distorci-da. Em uma modalidade, a necessidade de calcular a transformação em ca-da ponto de pixel pode ser evitada simplesmente calculando a transforma-ção para cada linha e utilizando uma interpolação linear para calcular as no-vas coordenadas de pixels. Após o mapeamento das novas coordenadasque correspondem a um documento tendo uma distorção de perspectiva re-duzida, uma reamostragem dos pixels é executada 815.

Outro aspecto da imagem recebida que pode ser ajustado nasetapas de remoção de distorção 240, 350 é um ajuste para as distorçõescausadas para lente de câmera 820. A distorção causada por uma lente decâmera pode fazer com que linhas de outro modo retas, curvem. Esta distor-ção depende da lente específica utilizada e da distância da câmera da ima-gem capturada. A curvaturã criada por distorção de lente será geralmenteradial e, portanto, um ajuste radial uniforme para a distorção de lente podeser executado utilizando um parâmetro que aproxima o grau de distorção delente. Este parâmetro pode ser ou calculado pelo sistema ou inserido pelousuário.

Ainda, outro aspecto da imagem recebida, que pode ser ajusta-do nas etapas de remoção de distorção 240, 350 é um ajuste para mais doque uma distorção. Por exemplo, se o documento de imagem formada foruma página de um livro como mostrado na Figura 18, a página de imagemformada terá uma superfície curva, que resulta em uma curvatura ou umadistorção de empeno. Também, pode existir uma distorção de perspectivaquando o documento de imagem formada é capturado a um ângulo oblíquoem relação à página. Estas distorções podem ambas ser corrigidas nas eta-pas de remoção de distorção 240, 350. Uma descrição detalhada de umamodalidade preferida para correção de distorção de imagens capturadas delivros e outros documentos e, se requerido, remover a distorção de perspec-tiva de tais imagens, está abaixo descrita em conexão com as Figuras 14-22.

Outras distorções podem também ser corrigidas e a descriçãode tipos específicos de distorção aqui não pretende limitar os tipos de distor-ção que podem ser reduzidos ou removidos.

Na etapa 365, um processo de limitação é executado sobre aimagem criada na etapa 360. O processo de limitação 360 reduz a profundi-dade de cor da imagem e tem a vantagem potencial de reduzir a distorçãocriada por um flash que pode ser utilizado quando fotografando a imagem.

Em uma modalidade, o processo de limitação 365 reduz as imagens de corde vinte e quatro bits para imagens preto e branco de um bit. Os benefíciospotenciais de reduzir as imagens para preto e branco é a redução dos efei-tos introduzidos pelo flash de câmera e a redução da quantidade de informa-ções requeridas para o sistema 300 processar. A limitação 365 pode ser e-xecutada em um número de modos. Uma modalidade pode utilizar uma téc-nica de pontilhamento, a qual é conhecida na técnica. Um exemplo de umatécnica de pontilhamento pode ser encontrado em um software de imagemexistente, tal como o SNOWBOUND®IMAGE LlBRARY pela SnoboundSoftware Corporation. Uma desvantagem de utilizar uma técnica de ponti-lhamento, no entanto, é a introdução de ruído na imagem. Outra modalidadepara a limitação 365 envolve selecionar um limite global para uma imagem.

Em tal técnica, um valor limite é selecionado. Aqueles pixels que tem umaintensidade maior do que o valor limite são considerados brancos e os pixelsrestantes são considerados pretos. O valor limite pode ser selecionado emum número de modos. Em uma modalidade, o valor limite é selecionado eaplicado para todas as imagens recebidas. Esta técnica tem a desvantagemde não considerar as condições de iluminação variadas nas imagens recebi-das. Em outra modalidade, o valor limite é calculado de uma análise da ima-gem recebida, tal como o seu histograma. Em tal modalidade que envolve aanálise da imagem recebida, uma suposição é feita de que a imagem rece-bida contém dois picos no seu histograma de intensidade que correspondemao plano dianteiro e ao plano traseiro da imagem de documento recebida.

Esta modalidade pode não funcionar bem para aquelas imagens às quais asuposição não se aplica. Outra modalidade para a limitação 365 é selecionarum valor limite separado para cada pixel na imagem recebida. Esta modali-dade tem a vantagem de responder a condições mutáveis dentro do docu-mento, tais como as mudanças de iluminação ou os contrastes de fundo.

Uma modalidade desta técnica é referida como limitação adaptável. Nestamodalidade, os valores de pixel anterior são considerados conforme cadanovo pixel é analisado para a determinação do valor limite. Um modo paraexecutar isto é calculando a média ponderada de cada pixel conforme cadapixel progressivo da imagem recebida é analisado. Uma desvantagem po-tencial desta modalidade é a introdução de ruído se a imagem recebidacompreender um documento colorido.

Na etapa 370 a etapa de linhas de texto é executada. Nesta eta-pa 370, o sistema determina as linhas de texto na imagem de documentorecebida. A Figura 9 apresenta uma modalidade das linhas de texto 370. Emuma modalidade, o sistema assume que os pixels que correspondem ao tex-to na imagem de documento recebida tem uma intensidade mais baixa doque os pixels de fundo da imagem de documento recebida. Nesta modalida-de, a soma das intensidades de todos os pixels dentro de cada uma das li-nhas da imagem de documento recebida é calculada 910. Estas somas sãoentão utilizadas para identificar os picos e vales locais na intensidade de pi-xel 920. Estes picos e vales são então analisados para determinar as linhasde texto no documento. Por exemplo, se a imagem de documento recebidativer linhas de texto pretas com um fundo branco, as linhas de pixels que sãointeiramente brancas terão as intensidades totais mais altas e as linhas quecontém o texto preto terão uma intensidade de pixel substancialmente maisbaixa. Estas diferenças em intensidade podem então ser calculadas e aslinhas de texto podem por meio disto ser determinadas. Em uma modalidadepreferida, a etapa de linhas de texto 370 é executada tanto horizontalmentequanto verticalmente através da imagem de documento recebida.

Outra modalidade para executar a etapa de linhas de testo 370 éexecutar uma pesquisa similar para as linhas de texto que são executadasna etapa 335. Em tal modalidade, o texto da imagem de documento captura-da é identificado e formado em linhas. Isto pode ser executado identificandoos componentes conectados na imagem de documento capturada e encon-trando o vizinho mais próximo destes componentes. Um componente conec-tado refere-se a um conjunto de pixels na imagem onde cada pixel é pretoou mais escuro e cada um está adjacente a pelo menos um outro pixel noconjunto. Os centros dos componentes conectados são então conectadosem linhas. Este processo é similar àquele descrito nas etapas 710, 720 e730 da Figura 7.

A etapa 375 determina se a imagem de documento capturadadeve estar em um formato de paisagem ou retrato. Em uma modalidade, istoé executado pela determinação se os componentes conectados adjacentesformam linhas de texto predominantemente verticais ou horizontais. O pro-cesso é operado uma vez onde as linhas de texto destacam-se de compo-nentes conectados, ou na direção horizontal ou na vertical, dependendo dadireção dos componentes conectados adjacentes. Em uma modalidade, adireção resultante com o maior número de linhas é determinada definir a ori-entação da imagem de documento recebida. Por exemplo, em uma imagemde documento recebida que tem uma altura maior do que a sua largura, seas linhas de texto 370 na direção vertical gerarem um maior número de li-nhas do que as linhas de texto 370 na direção horizontal, então o documentode imagem recebida é determinado ter uma orientação de paisagem. Comooutro exemplo, se no mesmo documento de imagem recebida as linhas detexto 370 na direção horizontal gerarem um maior número de linhas do queas linhas de texto 370 na direção vertical, então o documento de imagemrecebida é determinado ter uma orientação de retrato.

A etapa 380 determina a orientação aprumada do documento. AFigura 10 apresenta uma modalidade para determinar se a imagem de do-cumento recebida está apropriadamente orientada aprumada. Em uma mo-dalidade, cada linha de texto é analisada. Um menor de linhas de texto podeser analisado, mas isto pode resultar em um resultado menos confiável. Emuma modalidade, cada linha de texto está dividida em três seções na etapa1010: uma seção ascendente, uma seção média e uma seção descendente.

Os caracteres de idioma Inglês contêm certas características estatísticasinerentes que podem ser utilizadas em certas modalidades para determinara orientação aprumada da imagem de documento recebida. Por exemplo, oalfabeto de idioma Inglês tem somente cinco caracteres que descem abaixodo limite inferior de uma sentença (isto é, g, j, p, q e y) e tem muito mais ca-racteres que sobem acima do limite superior de uma sentença (por exemplo,b, d, f, h, i, k, I e t). Em uma modalidade, esta característica dos caracteresde idioma Inglês pode ser considerada quando calculando o respectivo nú-mero de pixels contidos na seção ascendente e seção descendente 1020 ecomparando estas densidades de pixels 1030, 1040. Por exemplo, uma ima-gem de documento recebida que tem caracteres de idioma Inglês que temmais pixels de caracteres ascendentes do que pixels de caracteres descen-dentes é provável estar na posição aprumada e não precisa ser girado, en-quanto que se o mesmo documento tiver mais pixels de caracteres descen-dentes do que pixels de caracteres ascendentes, o documento provavelmen-te precisa ser girado de cento e oitenta graus na etapa 1050.

Em outras modalidades, outras características de caracteres deidioma Inglês podem também ser consideradas. Por exemplo, as caracterís-ticas de localização de pixel na direção horizontal podem ser consideradas.Ainda, métodos não estatísticos podem também ser utilizados para determi-nar a orientação aprumada do documento, tal como o reconhecimento decaractere ótico ("OCR"). Outra modalidade poderia utilizar uma proposta derede neutra. Além disso, características inerentes similares podem ser utili-zadas para os documentos não em Inglês. Por exemplo, os caracteres deidioma Espanhol são similares àqueles em Inglês e terão características ine-rentes similares. Como outro exemplo, os caracteres de idioma Arábico con-tém um maior número de caracteres descendentes e as modalidades podemajustar-se a estas características conseqüentemente.

A Figura 12 apresenta outra modalidade para executar a etapa380 e determinar se a imagem de documento recebida está apropriadamen-te orientada aprumada. Em uma modalidade, os componentes conectadossão utilizados para determinar cada letra de linha de texto. Cada componen-te está classificado por altura, em duas categorias, pequena e grande 1210.O centro das linhas de texto é então determinado na etapa 1220. Em umamodalidade, as pequenas alturas de letra são utilizadas para determinar ocentro da linha de texto 1220 isto pode aperfeiçoar a estimativa do centro dalinha de texto se esta estiver distorcida, tal como se esta for curva através dapágina. As letras grandes são então correspondidas em relação ao centrodas linhas de texto, e são agrupadas como ascendentes ou descendentescom base na localização relativa de seu centro na etapa 1230. O númerototal de letras ascendentes e descendentes é então calculado na etapa1240. Em um documento de idioma Inglês típico, os caracteres grandes su-birão na direção do topo da página. Portanto, em uma modalidade, se o nú-mero de caracteres grandes ascendentes for maior do que o número daque-les descendentes, então o documento não precisa ser girado na etapa 385antes da emissão na etapa 390. Se, no entanto, o número de caracteresgrandes descendentes for maior do que o número de caracteres grandesascendentes, então o documento é girado na etapa 385 antes da emissãona etapa 390.

A imagem é então girada na etapa 385 de acordo com as deter-minações das etapas 380 e 375. Uma nova imagem de documento é entãoemitida na etapa 390.

Como acima discutido, os documentos de imagem formada desistema podem ser capturados ou em uma câmera de filme ou uma câmeradigital. Como uma alternativa a estes dispositivos de forma livre, um sistemade câmera estacionária pode ser empregado para capturar os documentosde imagem formada. A Figura 11 apresenta uma modalidade para um siste-ma de câmera estacionária para capturar uma imagem de documento. Nestamodalidade, o documento 1110 é colocado sobre a base 1120 do sistema.Em uma modalidade preferida, a base 1120 do sistema é de uma cor prede-terminada, o que pode ter a vantagem de facilitar o processo de segmenta-ção, acima discutido. Estendendo da base 1120 está o suporte 1130, o qualpode alojar uma câmera 1140 e uma iluminação 1150. A câmera e a ilumi-nação podem estar permanentemente alojadas dentro do suporte 1130 oupodem ser removíveis ou ajustáveis. A iluminação pode estar colocada emqualquer lugar sobre a base 1120 ou o suporte 1130. Em outra modalidade,nenhuma iluminação adicional é incluída na base 1120 ou no suporte 1130.Em ainda outra modalidade, a iluminação está separada da base 1120 ou dosuporte 1130. O sistema estacionário é então acoplado a um computador1160 para executar o processamento acima descrito do documento de ima-gem recebida. Em outra modalidade, o computador pode também estarconstruído dentro do aparelho. Em ainda outra modalidade, o documento deimagem capturada pode simplesmente ser armazenado na câmera digital1140 ou em outra fonte de memória e posteriormente acoplado a um compu-tador para processamento. Tal sistema de câmera estacionária pode ser co-locado como parte de uma estação de trabalho do usuário, por exemplo, emum escritório.

Existem diversas vantagens na utilização de um sistema de câ-mera estacionária em oposição a uma câmera de forma livre. Por exemplo,na utilização de um sistema de câmera estacionária, a quantidade de distor-ção de perspectiva pode ser reduzida, já que o documento é mais provávelestar perpendicular e centrado com relação à lente de câmera. Além disso,outra vantagem pode ser permitir que o sistema ajuste-se melhor para a dis-torção de lente, já que a distância entre a câmera e a lente utilizada seráconhecida, por meio disto reduzindo a necessidade de calcular ou aproximarestes parâmetros. Outra vantagem potencial seria reduzir as distorções cria-das por um flash de câmera. Em uma modalidade preferida, a iluminação1150 do sistema estacionário estaria posicionada de modo a reduzir o refle-xo e outras distorções criadas pelos flashes de câmera.

Apesar da utilização de um sistema de câmera estacionária po-der ser desejável, tais sistemas nem sempre serão práticos ou disponíveispara muitas necessidades de formação de imagem de documentos. Assim,um método para remover a distorção de imagem causada por uma superfíciedistorcida de um documento ou livro de imagem formada mesmo quando aimagem é capturada a um ângulo oblíquo seria extremamente útil. O proces-so de correção de distorção abaixo descrito em conexão com as Figuras 14-22 provê tal processo de remoção de distorção. Uma descrição detalhada deuma modalidade preferida para corrigir a deformação de imagens captura-das de livros e outros documentos e, se requerido, remover a distorção deperspectiva de tais imagens, está abaixo descrita em conexão com as Figu-ras 14-22.

O processo de correção de distorção da Figura 14 pode ser utili-zado para as etapas de remoção de distorção 240, 350 acima descritas nasFiguras 2 e 3. Alternativamente, este pode ser utilizado como uma técnica deprocessamento de formação de imagem independente, ou combinado cometapas selecionadas dos métodos descritos em conexão com as Figuras 2 e3, incluindo uma ou mais das etapas de segmentação e de orientação deimagem.O processo de correção de distorção mostrado na Figura 14compreende três etapas, as quais coletivamente transformam uma imagemde um documento distorcido em uma imagem correspondente do documentoplanificado. Isto é conseguido transformando o documento de imagem for-mada de um sistema de coordenadas curvas para um sistema de coordena-das Cartesianas. Na etapa 10 deste processo de correção de distorção ba-seado em modelo, uma rede de coordenadas curvas 132, como melhor vistona Figura 18, é aplicada a uma imagem 131 do documento distorcido quedeve ser transformado. Na etapa 11, a rede de coordenadas curvas 132 éestirada para formar uma rede de coordenadas retangulares 134 como mos-trado na Figura 19. Na etapa 12, a rede de coordenadas retangulares 134 naFigura 19 é ajustada para gerar uma rede de coordenadas retangulares ajus-tadas 136 como mostrado na Figura 21. A rede de coordenadas retangulares136 é de preferência bem proporcionada de modo que a distorção de ima-gem causada pela distorção do documento originalmente de imagem forma-da e/ou devido à perspectiva da câmera é reduzida, de preferência substan-cialmente reduzida, e mais de preferência completamente removida.

A rede de coordenadas curvas 132 na Figura 18 compreende ossegmentos de linha 33, 34, 37-39 e o eixo geométrico y 32. Os segmentosde linha 33, 34, 37-39 são uma porção de uma série de linhas retas concor-rentes, ao invés de paralelas, que geralmente estendem-se na direção doeixo geométrico y 32, mas as quais interceptam sobre um ponto de fuga co-mum o qual não está mostrado já que este está fora da figura. Assim, namodalidade ilustrada, os segmentos de linha concorrentes 33, 34, 37-39 es-tão mais separados uns dos outros nas suas porções inferiores e estão es-paçados mais próximos uns dos outros nas suas porções superiores. Ainda,como o grau de curvatura é maior próximo do eixo geométrico y 32, o quecorrespondem ao centro do livro de imagem formada, o espaço entre ossegmentos de linha é maior e quando mais estes afastam-se do eixo geomé-tricô y 32. Assim, o espaço entre os segmentos de linha 33 e 37 é maior doque espaço entre o eixo geométrico y 32 e o segmento de linha 38. Apesarde existir um número de método que podem ser utilizados para aplicar umarede de coordenadas curvas 132 a uma imagem 131 de um documento dis-torcido, dois métodos preferidos estão abaixo descritos em conexão com asFiguras 15-17. Em uma modalidade, os segmentos de linha concorrente 33,34, 37-39 e o eixo geométrico y 32 da rede de coordenadas curvas 132 sãodeterminados das coordenadas dos cantos das páginas de livro de imagemformada. A vantagem desta técnica é que esta é independente de texto naimagem capturada e assim permite que páginas que incluem imagens oufórmulas tenham a distorção corrigida.

Para cada ponto na Figura 18, a sua coordenada corresponden-te em um sistema de coordenadas Cartesiano pode ser decidida encontran-do a sua coordenada χ e y, respectivamente, sobre a rede de coordenadascurvas 132. Ainda, cada ponto sobre o mesmo segmento de linha (por e-xemplo, o segmento de linha P1Q1 39) na Figura 18 ao longo do eixo geomé-trico y 32, deve ter a mesma coordenada χ quando recuperado em uma ima-gem não distorcida. Também, cada ponto sobre o mesmo segmento de linhacurva ao longo do eixo geométrico χ 31 na Figura 18, deve ter a mesma co-ordenada y em uma imagem não distorcida. Em uma modalidade, a coorde-nada χ de cada pixel sobre a página de imagem formada é decidida traçandouma linha do ponto de fuga através daquele pixel e interceptando com aborda inferior 35 da página de livro na imagem 131. A distância entre a inter-seção e o eixo geométrico y 32 é então a coordenada χ daquele pixel.

No entanto, é mais complexo determinar a coordenada y de ca-da pixel sobre a rede de coordenadas curvas 132. Um método que pode serutilizado é dividir cada um dos segmentos de linha reta concorrentes 33, 34,37-39 que estendem-se na direção do eixo geométrico y 32 em muitas pe-quenas seções. As Figuras 20 e 22 são úteis na explicação deste processo.A Figura 20 apresenta uma projeção da imagem de livro na imagem 131(mostrada na Figura 18) sobre a superfície de página 142 do livro que teve aimagem formada. Apesar dos pontos P(x) e Q(x) estarem localizados emdois dos cantos opostos da superfície de página 142, deve ser compreendi-do que P(x) pode estar localizado em qualquer ponto sobre a borda curvasuperior 144 e Q(x) está localizado na interseção do segmento de linha so-bre o qual Ρ(χ) fica e a borda curva inferior 146 da superfície de página 142.

O mesmo aplica-se a P'(x) e Q'(x) mostrados na imagem 131.

A Figura 22 é uma vista lateral da projeção para o segmento delinha P1Q1 39 sobre a rede de coordenadas curvas 132 na Figura 18 para osegmento de linha PQ 49 correspondente sobre a superfície de página 142do livro de imagem formada. Assim, o segmento de linha P'Q' 39 na Figura22 está sobre o plano de imagem 67 e estende-se na direção do eixo geo-métrico y 32 e o segmento de linha PQ 49 é a projeção de P1Q1 39 sobre asuperfície de página 142. Deve ser notado que o segmento de linha PQ 49sobre a superfície de página 142 na Figura 22 também corresponde aosegmento de linha PQ 49 sobre a rede retangular 134 na Figura 19.

No diagrama de projeção da Figura 22, S corresponde à lente 66a qual é utilizada para capturar a imagem 131 da superfície de página 142do livro de imagem formada. O eixo geométrico ótico da lente 66, ó qual cor-responde ao eixo geométrico ζ 65 na Figura 22, intercepta o plano de ima-gem 67 em O e a superfície de página 142 em R. H e I são os pontos de pro-jeção de P e Q sobre o eixo geométrico ζ 65, respectivamente. Assim, se ZPRH = Θ, por geometria, as seguintes equações podem ser derivadas:

<formula>formula see original document page 25</formula>

(EQUAÇÕES A)

Para resolver para ΡΌ,

<formula>formula see original document page 25</formula>

Ainda, determinando SO = f, SR = d, P1O = yp·, o qual é a coor-denada y do ponto P1 na Figura 18, PR = yp, o qual é a coordenada y do pon-to P na Figura 19, então a equação (1) pode ser reescrita como

<formula>formula see original document page 25</formula>

Aqui f, d, e θ podem ser considerados constantes se for assumi-do que a distância da lente de câmera 66 para todos os pontos sobre o livrofor a mesma. Portanto, a equação (2) pode ser simplificada fazendo<formula>formula see original document page 26</formula>

Substituindo a e b na equação (2) resulta na equação (3) abaixo.

<formula>formula see original document page 26</formula>

(EQUAÇÃO 3)

A equação (3) é a função de transformação para a coordenada yentre P e P'. Analogamente, fazendo Q'0 = yq·, QR = yq, então a equaçãopara QeQ' pode ser derivada:

<formula>formula see original document page 26</formula>

(EQUAÇÃO 4)

Referindo de volta à Figura 19, fazendo Po, Pi, P2, ··· Pn seremn+1 pontos separados uniformemente sobre o segmento de linha PQ 49.

Cada ponto P, tem uma coordenada y a qual pode ser representada pelascoordenadas y do ponto P e do ponto Q. Para cada ponto Pi, temos:

<formula>formula see original document page 26</formula>

(EQUAÇÃO C)

em que i é 0, 1, 2, ... n. Combinando com a Equação (4), agora temos todasas coordenadas y sobre o plano de imagem P0, Pi, P2, ■■■ Pn:

<formula>formula see original document page 26</formula>

(EQUAÇÃO 5)

Utilizando a equação (5) o segmento de linha P1Q1 39 é divididoem η seções. Dividindo todos os segmentos de linha ao longo do eixo geo-métrico y, a rede retangular desproporcional 134 na Figura 19 é ajustada pormapeamento de pixel para pixel da rede de coordenadas curvas 132 da Fi-gura 18.

Apesar da rede retangular 134 na Figura 19 ter segmentos delinha verticais paralelos 43-44, 47-49 e segmentos de linha horizontais para-lelos 45, 46, o espaço entre os segmentos de linha 43 e 47 é maior do que oespaço entre o eixo geométrico y 42 e o segmento de linha 48. Portanto, aetapa 12 seguinte no processo de correção de distorção é ajustar a larguraentre os segmentos de linha verticais paralelos 43, 44, 47-49 da rede retan-guiar desproporcional 134.

Referindo à Figura 23, considere a superfície de livro da páginacomo uma superfície como cilindro, se o livro for visto do lado inferior, estedeve ter uma superfície de página curva direita 91 e uma superfície de pági-na curva esquerda 92. Na Figura 23, a brochura de livro 80 está localizadana origem e o livro está localizado sobre o plano x-y. As bordas laterais delivro 83, 84 estão mostradas como pontos na vista lateral. O segmento delinha PaQa 89 está também mostrado como um ponto que tem uma distânciabpq 86 de PQ 90 (também mostrado como um ponto) sobre o eixo geométri-co χ 81. Para considerar a página direita e a página esquerda separadamen-te, utilizamos uma função indeterminada b(x) 82 que pode ser utilizada pararepresentar todos os pontos sobre a superfície de página de livro curva direi-ta 91. Portanto, no ponto de origem 80, b(0) = 0.

Referindo à Figura 24 para uma descrição detalhada do ajustepara a distância de lente para objeto. Na Figura 24, PaQa 78 é um segmentode linha sobre a superfície de página curva 142 e Ra é o ponto sobre a inter-seção de PaQa 78 e o eixo geométrico ζ 75. PaQa 78 e o eixo geométrico ζ75 formam um ângulo de θ 71. O segmento de linha ajustado PaQa 78 é pa-ralelo a PQ 74 onde o segmento de linha PQ 74 intercepta o eixo geométricoz 75 em R. A distância entre o segmento de linha PQ 74 e o segmento delinha PaQa 78 é bpq 72. Portanto, por trigonometria, o comprimento do seg-mento de linha RaR 73 é bpq/sen0.

Referindo de volta à Figura 22, podemos agora ajustar a distân-cia da lente 66 para a superfície de página 142 subtraindo b(x)/sen0 de SRjá que existe uma distância da superfície de página 142 para a mesa excetona espinha de livro e nas bordas laterais de livro. Como um resultado, d(x) =d(0) - b(x)/sen0. Substituindo esta equação na equação (2), resulta:<formula>formula see original document page 28</formula>

(EQUAÇÕES D)

Assumindo que b(x) « d + Ypcos0,

<formula>formula see original document page 28</formula>

(EQUAÇÕES 6)

onde C é uma constante já que f, d(0), Geyp são todos constantes uma vezque a imagem é capturada. E yp(x) é a função de linha de borda superior 36a qual foi decidida na etapa 320, 335. Aplicando a equação (6), pode-se ago-ra resolver para b(x).

Referindo de volta à Figura 23, o eixo geométrico χ 81 pode serdividido em muitos segmentos pequenos. Para cada segmento pequeno Δχ87 sobre o eixo geométrico χ 81, existe um arco 88 correspondente sobre asuperfície de página 91. O comprimento do arco 88 aproxima de um valorAArc o qual é igual a (Δχ2 + Ab2(x))1/2 se Δχ for muito pequeno. Assim, fa-zendo j(x) corresponder ao comprimento de um arco da origem 80 paraqualquer ponto sobre a superfície de página 91, então a seguinte equaçãopode ser descrita:

<formula>formula see original document page 28</formula>

(EQUAÇÃO E)

Uma fórmula similar pode ser escrita para a superfície de página92. Uma vez que j(x) é obtido, a rede retangular 134 na Figura 19 pode serajustada para uma rede retangular bem proporcionada 136 como mostradona Figura 21.

Na Figura 21, a página de livro mostra o resultado de uma trans-formação de correção de distorção da página de livro da Figura 18. Estesresultados foram obtidos utilizando uma imagem com uma resolução de2304 χ 1704 e aproximadamente 200 dpi. A distância entre a lente e a super-fície de página era de aproximadamente 50 cm. O ângulo entre a lente a su-perfície de livro era menor do que 30 graus. Ainda, a taxa OCR resultanteera de aproximadamente 90%.

Apesar do processo de correção de distorção acima descritofuncionar melhor quando o fundo é uma cor escura, outros fundos podemser empregados. A modalidade de correção de distorção apenas descrita émuito útil para a remoção de distorções de um documento de imagem for-mada que tem distorções tanto de curvatura quanto de perspectiva, mesmoquando o documento de imagem formada compreende relativamente poucaslinhas de texto.

Um método preferido para gerar a rede de coordenadas curvas132 será agora descrito em conexão com as Figuras 15 e 16.

Quando um livro é aberto, as superfícies de página tipicamentenão ficam planas, especificamente quando o livro é espesso, e, como umresultado, as linhas de texto tornam-se curvas. No método da Figura 15, aslinhas de texto mais longas sobre uma página de imagem formada são Ioca-lizadas. Uma transformação baseada nas linhas de texto mais longas, maisamplamente separadas é então executada, a qual pode por sua vez ser utili-zada para gerar a rede de coordenadas curvas 132.

O método para gerar a rede de coordenadas curvas 132 mostra-do na Figura 15 inclui quatro etapas principais. Primeiro, uma etapa de seg-mentação de área de texto 1 é utilizada para separar a área em uma ima-gem armazenada de uma página de livro que contém um texto. Segundo,uma etapa de melhoramento de direção local 2 é utilizada para revelar aslinhas de texto ocultas. Terceiro, uma etapa de extração de linha de texto 3 éutilizada para estimar uma curva de esqueleto para cada linha de texto. Aúltima etapa é o coletamento de linha de texto 4, a qual é utilizada para sele-cionar uma função polinomial adequada para representar as linhas de texto.

Em uma modalidade, a área de texto de um documento de ima-gem formada é assumida compreender uma grande área de espaço clarocom alguns caracteres escuros ou figuras na mesma. De modo a separar aárea de texto na etapa 1, uma miniatura de tamanho pequeno da imagemoriginal é gerada. Cada pixel na miniatura é ajustado para preto se todos ospixels que esta representa na imagem original forem escuros, de outro modoo pixel é ajustado para branco. Com a imagem em miniatura, é então possí-vel prontamente procurar pelos maiores pixels brancos conectados, os quaiscorresponderão à área de página do livro ou documento de imagem forma-da. Este processo separa a imagem da página de livro ou documento de seufundo, e assim constitui um método alternativo para executar as etapas desegmentação 230, 355. Uma vez que a página de livro ou documento é se-parado de seu fundo, a área de texto sobre a página de imagem formada éidentificada. Para executar isto, outra miniatura pode ser gerada, de prefe-rência utilizando um método de amostragem inversa, a saber, cada pixel naminiatura é ajustado para branco se este estiver na área de página de ima-gem formada e a área que este cobre na imagem original tiver uma alta vari-ância de intensidade e pelo menos um pixel escuro. Como um resultado, asáreas brancas nesta miniatura representam as áreas de texto na imagemoriginal. Em outra modalidade ilustrada na Figura 25, uma miniatura 450 égerada em que cada pixel na miniatura 450 é ajustado para preto se esteestiver na área de página e a área que este cobre na imagem original tiveruma alta variância de intensidade e pelo menos um pixel escuro. Como umresultado, as áreas pretas nesta miniatura 450 representam as áreas de tex-to na imagem original.

Após a área de texto ser obtida, a etapa de segmentação de á-rea de texto 1 está pronta para ser executada. Isto é especialmente útilquando lidando com uma imagem de um livro aberto, a qual tipicamentecompreenderá duas páginas. É também útil para a segmentação de colunasde texto sobre uma página de imagem gerada. Em uma modalidade, a seg-mentação é executada pelo escaneamento da miniatura 450 ao longo delinhas verticais 454 da área de página na imagem de miniatura 450 para i-dentificar os espaços entre as áreas de texto detectando se cada pixel namesma linha vertical é um pixel branco (ou um pixel escuro se o método deamostragem inversa for utilizado). Se a resposta for positiva, então a linhavertical inteira está ficando sobre um espaço entre a área de texto. Um limiteapropriado separará a maioria das áreas de texto (por exemplo, uma páginade imagem formada de outra página de imagem formada quando duas pági-nas de um livro são capturadas na mesma imagem e/ou algumas colunas detexto sobre a mesma página de imagem formada).

Na etapa 2, um melhoramento de direção local é de preferênciaexecutado. Apesar das pessoas lerem os livros "linha por linha", não existemlinhas geométricas em uma linha de texto. Ao contrário, as pessoas compre-endem que dois caracteres diferentes pertencem à mesma linha de textodevido à densidade de caracteres, as suas direções, e significados de texto.

No entanto, um computador não sabe a direção de caracteres e os seus sig-nificados. A única informação disponível para um processador de imagem éa direção local de caracteres com base em suas densidades. Em uma moda-lidade, a etapa de melhoramento de direção local 2 é executada para revelaras linhas de texto ocultas pela computação das densidades de cada caracte-re. A Figura 16 mostra um fluxograma de um processo para executar a etapade melhoramento de direção local 2, a qual ainda contém quatro subetapas.

Primeiro, uma etapa de detecção de distância de linha de texto 5é de preferência executada para detectar a altura de linhas de texto. A alturade linha de texto é um fator importante na determinação da taxa de com-pressão para a próxima etapa 6. Na etapa 6, a imagem de entrada é com-primida e convertida em uma imagem binária. A seguir, na etapa 7, um pro-cesso é utilizado para computar e melhorar uma matriz de direção, a qualrepresenta a direção local de cada pixel em uma imagem. Em uma modali-dade, dezesseis gabaritos direcionais predefinidos são utilizados para esti-mar a direção de cada pixel. Após a matriz de direção ser calculada paracada pixel, um algoritmo de uniformização é utilizado para eliminar o ruídona matriz. Na etapa 8, um melhoramento baseado em matriz de direção éexecutado. A matriz de direção e a imagem original são utilizadas para fazerum melhoramento de direção local de modo a eliminar quaisquer espaçosentre as palavras na mesma linha de texto e por meio disto gerar uma linhade texto contínua. Uma imagem de escala de cinza é obtida do processo demelhoramento acima descrito, a qual é subseqüentemente processada naetapa de extração de linha de texto 3 da Figura 15.

Na etapa de extração de linha de texto 3, a imagem da etapa 2 éconvertida em uma imagem binária. Uma descrição detalhada de cada umadas subetapas 5, 6, 7, 8 da etapa de melhoramento de direção local 2 estáabaixo provida.

De preferência a etapa de detecção de distância de linha de tex-to 5 da Figura 16 é executada pela geração de uma imagem de miniaturasimilar àquela utilizada na etapa de detecção de área de texto 1. Em umamodalidade, uma imagem de miniatura a qual é quatro vezes mais alta emresolução vertical do que na etapa 1 é utilizada. A área de texto é então divi-dida em uma pluralidade de segmentos menores. Isto está ilustrado nas Fi-guras 26A e 26B. A Figura 26A apresenta um segmento pequeno 460 deuma imagem de texto. A Figura 26B apresenta uma imagem de miniatura daimagem da Figura 26A. Para cada miniatura 464 que corresponde a umsegmento 460 de área de texto, uma faixa retangular de pixels 462 na por-ção central da miniatura 464 é selecionada. Esta faixa retangular de pixels462 é de preferência ajustada para ter a mesma altura que o segmento 460de área de texto que está sendo analisada, mas de preferência ocupa so-mente 1/32 da largura de todo o segmento 460. Cada faixa retangular 462 éentão verticalmente escaneada de cima para baixo quando escaneando ca-da faixa retangular 462. Se existir um pixel o qual é considerado constituirum texto, cada pixel no mesmo nível horizontal do escaneamento pode tam-bém ser tratado como texto. Portanto, muitas áreas retangulares 46 podemser geradas dentro da faixa 462. Com base no escaneamento da faixa 462,o número de linhas de pixel L com pelo menos um pixel preto é contado. A-lém disso, o número total de linhas de texto C é contado. Portanto, uma altu-ra bruta de linhas de texto H0 para cada área de texto é igual a UC para a -quela área de texto. Para tornar a estimativa mais precisa, o cálculo de altu-ra pode ser repetido, enquanto filtrando estas linhas com um valor de l_/Cmaior do que 2H0. Esta etapa de filtragem pode ser utilizada para livrar-se deelementos tais como as imagens. O resultado final desta análise é a alturade texto H. Do mesmo modo, o espaço médio S entre as linhas de texto po-de ser calculado. Finalmente, a distância entre as linhas de texto é simples-mente a soma de S e H.

Na etapa 6 da Figura 16, um processo para comprimir a imagemde entrada e convertê-la em um mapa binário é de preferência executado.Com base na distância calculada entre as diferentes linhas de texto da etapa5, é possível selecionar uma taxa de compressão para que a imagem deentrada possa ser comprimida de modo que os caracteres na mesma linhaconectem-se, mas os caracteres não na mesma linha fiquem separados. Emuma modalidade, um algoritmo binário local é então executado. Primeiro, aimagem de entrada é dividida em janelas pequenas de acordo com a taxa decompressão desejada. Então, para cada janela, o pixel mais escuro é identi-ficado. Se o valor de cinza do pixel mais escuro for maior do que um valorlimite, ou maior do que um segundo valor limite mais o valor de cinza médioda janela pequena, então o valor de cinza para cada pixel na mesma janelaé ajustado para 255. De outro modo, cada pixel na janela é ajustado para 0.

Na etapa 7 da Figura 16, um processo para computar e unifor-mizar uma matriz de direção é executado. Em uma modalidade, dezesseisgabaritos direcionais de 9x9 predeterminados podem ser utilizados para es-timar a direção de cada pixel. As Figuras 27A-F apresentam seis de dezes-seis gabaritos direcionais de 9x9 que podem ser utilizados para executar aetapa 7 da Figura 16. Nas Figuras 27A-F, o bloco preto 474 no centro dogabarito direcional de 9x9 470 representa o pixel central, enquanto que osoito blocos cinza 472 descrevem uma direção do pixel central. Assim, porexemplo, a Figura 27A representa uma linha de texto com uma direção verti-cal enquanto que a Figura 27E representa uma linha de texto inclinando a 45graus com a horizontal. Os padrões dos outros dez gabaritos direcionais quepodem ser utilizados na execução da etapa 7 podem ser derivados da ten-dência dos seis primeiros gabaritos direcionais como mostrado nas Figuras27A-F (isto é, os blocos cinza deslocam-se no sentido horário um por um).Com estes dezesseis gabaritos direcionais de 9x9, a etapa 7 de computar amatriz de direção pode ser executada.

Primeiro, para cada pixel na página de imagem formada, dezes-seis somas de valores de nível de cinza em todas as dezesseis direçõesprovidas pelos dezesseis gabaritos direcionais de 9x9 são calculadas. A se-guir, a soma máxima, mínima, e média de valores de nível de cinza as quaisestão denotadas por sum_max, sum_min, e sum_avg são determinadas.

Cada soma de valores de nível de cinza está representada pela soma dopixel central (bloco escuro) e oito pixels (blocos cinza) definidos por um dosdezesseis gabaritos direcionais. O valor de sum^max representa a maior dasdezesseis somas de valores de nível de cinza. O valor de sum_min é a me-nor das dezesseis somas de valores de nível de cinza. O valor de sum_avgé a média de todas as dezesseis somas de valores de nível de cinza. A dire-ção indicada pelo gabarito direcional o gera o sum_min implica em que opixel central está localizado sobre uma linha de texto e a direção do pixelcentral está representada por aquele gabarito direcional. Pela mesma razão,a direção indicada pelo gabarito direcional o qual gera o sum_max implicaque o pixel central não está localizado sobre uma linha de texto e a direçãodo pixel central está representada por aquele gabarito direcional. Disto, adireção de cada pixel pode ser determinada.

Em uma modalidade, a direção de um pixel é ajustada compa-rando o valor de cinza do pixel (i,j) (gray_value (i,j)) como segue: se9*gray_value (i,j) + sum_max + sum_min > 3*sum_avg, então a direção nopixel é ajustada para a direção do gabarito direcional de 9x9 o qual gerou osum_max, de outro modo, a direção do pixel é ajustada para a direção dogabarito direcional de 9x9 o qual gerou o sum_min. A direção estimada decada pixel forma uma matriz de direção. No entanto, devido à complexidadede caracteres no bloco de imagem, as direções de alguns pixels podem nãoser corretas. Por exemplo, a direção de um bloco vazio é inútil para revelaras linhas de texto. Conseqüentemente, em uma modalidade, um algoritmode uniformização é utilizado para ajustar a direção de todos os pixels namesma linha vertical para terem a mesma direção. Isto pode ser feito execu-tando um processo de votação, o que significa que a direção mais comumentre os pixels em qualquer linha vertical deve tornar-se a direção de cadapixel na mesma linha vertical.

Na etapa 8 da Figura 16, um processo para executar um melho-ramento baseado em matriz de direção é executado. As Figuras 28A e B sãoúteis para ilustrar uma modalidade da etapa de melhoramento baseado emmatriz de direção 8 da Figura 16. A Figura 28A apresenta uma imagem detexto. A Figura 28B apresenta a matriz de direção gerada da imagem mos-trada na Figura 28A após a execução das etapas de melhoramento baseadoem matriz de direção da Figura 16.

Conhecendo a direção de cada pixel, os espaços 480 entre oscaracteres que pertencem à mesma linha de texto podem ser eliminados.Isto pode ser executado tirando a média do valor de cinza de cada pixel comos seus pixels vizinhos e utilizar o valor de cinza médio para representar opixel. Então, o valor de cinza é ajustado ou para 0 ou 255 dependendo dovalor limite. Em uma modalidade, a média dos valores de cinza é tirada comoito pixels mais próximos do mesmo. Após este processo, a maioria dos es-paços entre os caracteres vizinhos estão preenchidos e os esqueletos delinhas de texto 482 são gerados, por meio disto resultando na imagem me-Ihorada mostrada na Figura 28B.

Referindo de volta à Figura 15, a etapa de extração de linha detexto 3 é agora utilizada para estimar a curva de esqueleto para cada linhade texto revelada na etapa anterior. Referindo à Figura 29A, as linhas detexto 490 reveladas na etapa anterior são muito grossas para extrair. Portan-to, um processo de afinamento é de preferência executado sobre as linhasde texto 490 para gerar as linhas de texto melhoradas 492 mostradas naFigura 29B. O processo de afinamento é executado para tornar a altura decada linha de texto melhorada 492 do tamanho de um pixel. Isto pode serexecutado escaneando verticalmente no sentido de pixel sobre os esquele-tos de linhas de texto 490 na Figura 29A. Por exemplo, quando um pixel es-curo é encontrado, a sua coordenada y pode ser gravada como y_start. En-tão os pixels abaixo deste são escaneados um por um até que um pixelbranco seja encontrado. Um y_end pode ser gravado para o pixel logo acimado pixel branco. Portanto, as coordenadas y para a linha de afinamento ex-traída pode ser ajustada como (y_start + y_end)/2. O resultado deste pro-cesso de afinamento são as linhas de texto melhoradas 492 como mostradona Figura 29B. Um processo de traçagem de linha de texto que inclui as se-guintes subetapas é então de preferência executado para completar a etapa 3.

A Figura 30 apresenta os esqueletos de linhas de texto afinadas492 com uma banda de detecção vertical 642 que pode ser utilizada paraexecutar o processo de traçagem de linha de texto. Em uma modalidade,cada linha de texto afinada é detectada pelo ajuste de uma banda de detec-ção vertical 642 no meio da página. Isto detectará a maioria das linhas detexto longas 646. Detectando se os valores de cinza em pixels sobre a ban-da de detecção são pretos, o ponto médio de cada linha de texto pode sercoletado. Após conseguir cada ponto médio de linhas de texto, cada linha detexto do ponto médio é traçado tanto na direção esquerda quanto na direita.

Para traçar uma linha de texto na direção esquerda, uma linha de traço deinclinação K (iniciando de 0) para traçar 0 a 12 pixels na esquerda. Se existirum pixel preto dentro de 3 pixels acima ou abaixo desta linha de traço, esteponto é considerado como um ponto da linha de texto. Este ponto é gravadoe o próximo ponto sobre a linha é determinado. Quando o novo ponto é en-contrado, uma nova inclinação é calculada para o propósito de continuar oprocesso de traçagem. Uma nova inclinação K pode ser decidida pela equa-ção de K = 10*K_previous/11 + 10*(y_new_y_previous)/(x_new_x_previous),onde, x_previous e y_previous são as coordenadas χ e y do ponto previa-mente coletado sobre uma linha de texto e x_new e y_new são as coorde-nadas χ e y do ponto correntemente coletado sobre uma linha de texto. Esteprocesso pode ajustar a direção de traçagem e ajustará as variedades dadistorção de linhas de texto. O processo é repetido até encontrar a borda dalinha de texto ou esgotar os pontos. Apesar do processo acima ser para tra-çar a parte esquerda de uma linha de texto, o traço para a parte direita é si-métrico. Se existirem ainda algumas linhas de texto não contínuas após esteprocesso, um algoritmo de coletamento auto-adaptável pode ser utilizadopara traçar cada linha de texto.

A etapa 4 na Figura 15 compreende a etapa de seleção de li-nhas de texto e de cálculo de um polinômio para gerar a rede de coordena-das curvas 132. As Figuras 31A e 31B são úteis para ilustrar um método pa-ra executar esta etapa. A Figura 31A apresenta uma imagem de linha detexto e a Figura 31B apresenta uma imagem de linha de texto com uma so-breposição de linha de texto extraída sobre a mesma. Na etapa 4, as linhasde texto 650 que são mais curtas do que uma quantidade predefinida daslinhas de texto mais longas 644, 648 são removidas. De preferência, aquelasque são menores do que a metade do comprimento das linhas mais longas644, 648 são removidas. Além disso, as linhas 656 com endentação esquer-da são também de preferência removidas. Duas das linhas restantes maislongas 644, 648 são selecionadas. Em uma modalidade, duas das linhasmais separadas são utilizadas. Os pontos de extremidade 632, 634, 636,638 destas duas linhas 644, 648 determinam as duas bordas de texto nolado esquerdo 652 e no lado direito 654 do documento de imagem formada.

A linha de borda esquerda 652 e a linha de borda direita 654 devem inter-ceptar em um ponto de fuga o qual está fora da figura e não está mostrado.

Finalmente, uma função polinomial pode ser utilizada para modelar as linhasde texto 644, 648 selecionadas. Em uma modalidade, a função polinomial éajustada para a quinta ordem.

Uma vez que a função polinomial destas linhas de texto é obtida,a rede de coordenadas curvas 132 pode ser gerada para executar o proces-so de correção de distorção da Figura 14. Em uma modalidade, uma vez quea função polinomial para estas linhas de texto é obtida, um processo de ex-tensão de linha é executado para estender as linhas de texto 644, 648 sele-cionadas para a sua esquerda e direita para manter uma margem em cadalado da área de texto. O grau de extensão pode ser formulado com base nalargura da área de texto. As linhas estendidas podem também ser ajustadaspara a função polinomial previamente obtida. As duas extremidades direitasdas linhas estendidas definem uma linha a qual deve passar pelo ponto defuga e as duas extremidades esquerdas das linhas estendidas também defi-nem uma linha a qual deve também passar pelo ponto de fuga. Uma vez queas linhas estendidas são obtidas, a rede de coordenadas curvas 132 podemser gerada para executar o processo de correção de distorção da Figura 14.

Outro método preferido para gerar a rede de coordenadas cur-vas 132 será agora descrito em conexão com a Figura 17.

O método da Figura 17 pode extrair os cantos, e mais importan-temente, as funções das bordas superior e inferior curvas de uma superfíciede página curva de um livro. Referindo à Figura 17, os seis cantos 21-26 daspáginas de um livro de imagem formada podem ser calculados encontrandoos pontos de interseção de linhas de borda 19, 20, 27-30. Note que na Figu-ra 17, as bordas superiores 27, 28 são linhas curvas como são as bordasinferiores 29, 30. Duas bordas laterais 19, 20 são linhas retas. Em uma mo-dalidade, o cálculo dos seis cantos 21-26 e das linhas de borda 19, 20, 27-30 é determinado como abaixo descrito e ilustrado nas Figuras 32 e 33. Pri-meiro, a resolução da imagem original é reduzida, de preferência para100x100 e então convertida em uma imagem preta e branca 676 pela utiliza-ção de um limite de nível de cinza. A área cinza 660 representa o fundo e aárea branca 674 representa uma área de página. Segundo, as bordas 670-673 da área branca são encontradas e os vértices 662, 664, 666, 668 dasquatro bordas 670-673 são especificados. Terceiro, a borda superior 672 e aborda inferior 670 são utilizadas como linhas de guia para abrir uma série dejanelas pequenas ao longo da borda superior 672 e da borda inferior 670.

Quarto, uma detecção de borda Canny é executada sobre as janelas peque-nas e o resultado da detecção é combinado em duas imagens curvas, umapara a borda superior 684 e uma para a borda inferior 682. Estas duas ima-gens curvas 684, 682 desejavelmente tem uma largura a mesma que a lar-gura da janela pequena acima mencionada. Quinto, as bordas das imagenssão traçadas para terem as bordas curvas superiores 686, 687 e as bordascurvas inferiores 688, 689.

Referindo de volta à Figura 17, as bordas curvas superiores são27, 28 e as bordas curvas inferiores são 29, 30. Os pontos de extremidadeda borda curva superior e da borda curva inferior definem os quatro cantos21-24. A conexão dos dois cantos direitos 22, 24 fará uma borda direita 19do livro e a conexão dos dois cantos esquerdos 21, 23 fará uma borda es-querda 20 do livro. O ponto de curvatura máxima 25, 26 em cada uma daborda curva superior 27, 28 e da borda curva inferior 29, 30 torna-se os doisoutros cantos 25, 26 e uma conexão entre estes dois cantos 25, 26 compre-ende a espinha do livro e o eixo geométrico y na rede de coordenadas cur-vas 132. As projeções da borda direita 19 e da borda esquerda 20 podemser utilizadas para encontrar o ponto de fuga e com isto gerar a rede de co-ordenadas curvas 132.

As propostas aqui descritas para processar uma imagem captu-rada são aplicáveis a qualquer tipo aplicativo de processamento e (sem limi-tação) estão especificamente bem adequadas para os aplicativos baseadosem computador para processar as imagens capturadas. As propostas aquidescritas podem ser implementadas em circuito de hardware, em softwarede computador, ou uma combinação de circuito de hardware e de softwarede computador e não estão limitadas a nenhuma implementação de hardwa-re ou de software específica.

A Figura 13 é um diagrama de blocos que ilustra um sistema decomputador 1300 sobre o qual as modalidades da invenção acima descritaspodem ser implementadas. O sistema de computador 1300 inclui uma barracondutora 1345 ou outro mecanismo de comunicação para comunicar asinformações, e um processador 1335 acoplado com a barra condutora 1345para processar as informações. O sistema de computador 1300 também in-clui uma memória principal 1320, tal como uma memória de acesso randô-mico (RAM) ou outro dispositivo de armazenamento dinâmico, acoplado nabarra condutora 1345 para armazenar as informações e as instruções a se-rem executadas pelo processador 1335. A memória principal 1320 tambémpode ser utilizada para armazenar as variáveis temporárias ou outras infor-mações intermediárias durante a execução de instruções a serem executa-das pelo processador 1335. O sistema de computador 1300 ainda inclui umamemória somente de leitura (ROM) 1325 ou outro dispositivo de armazena-mento estático acoplado na barra condutora 1345 para armazenar as infor-mações e as instruções estáticas para o processador 1335. Um dispositivode armazenamento 1330 tal como um disco magnético ou um disco ótico,está provido e acoplado na barra condutora 1345 para armazenar as infor-mações e as instruções.

O sistema de computador 1300 pode estar acoplado através dabarra condutora 1345 a um display 1305, tal como um tubo de raios catódi-cos (CRT), para exibir as informações para um usuário de computador. Umdispositivo de entrada 1310, que inclui teclas alfanuméricas e outras, estáacoplado na barra condutora 1345 para comunicar as informações e as se-leções de comando para o processador 1335. Outro tipo de dispositivo deentrada é um controle de cursor 1315, tal como um mouse, um trackball, outeclas de direção de cursor para a comunicação de informações de direçãode seleções de comando para o processador 1335 e para controlar o movi-mento de cursor no display 1305. Este dispositivo de entrada tipicamentetem dois graus de liberdade em dois eixos geométricos, um primeiro eixogeométrico (por exemplo, x) e um segundo eixo geométrico (por exempio, y),que permitem que o dispositivo especifique posições em um plano.

Os métodos aqui descritos estão relacionados com a utilizaçãodo sistema de computador 1300 para processar uma imagem capturada. Deacordo com uma modalidade, o processamento da imagem capturada é pro-vido pelo sistema de computador 1300 em resposta ao processador 1335executando uma ou mais seqüências de uma ou mais instruções contidas namemória principal 1320. Tais instruções podem ser lidas para a memóriaprincipal 1320 de outro meio legível por computador, tal como o dispositivode armazenamento 1330. A execução das seqüências de instruções conti-das na memória principal 1320 faz com que o processador 1335 execute asetapas de processo aqui descritas. Um ou mais processadores em uma dis-posição de múltiplo processamento podem também ser empregados paraexecutar as seqüências de instruções contidas na memória principal 1320.

Em modalidades alternativas, um circuito com fiação pode ser utilizado nolugar das ou em combinação com as instruções de software para implemen-tar as modalidades aqui descritas. Assim, as modalidades aqui descritas nãoestão limitadas a nenhuma combinação específica de circuito de hardware ede software.

O termo "meio legível por computador" como aqui utilizado, refe-re-se a qualquer meio que participe na provisão de instruções para o pro-cessador 1335 para execução. Tal meio pode tomar muitas formas, incluin-do, mas não limitado a, meios não voláteis, meios voláteis, e meios detransmissão. Os meios não voláteis incluem, por exemplo, os discos óticosou magnéticos, tal como o dispositivo de armazenamento 1330. Os meiosvoláteis incluem uma memória dinâmica, tal como a memória principal 1320.

Os meios de transmissão incluem os cabos coaxiais, os fios de cobre e asfibras óticas, incluindo os fios que compreendem a barra condutora 1345. Osmeios de transmissão podem também tomar a forma de ondas acústicas oude luz, tais como aquelas geradas durante as comunicações de dados deondas de rádio e infravermelho.

As formas comuns de meios legíveis por computador incluem,por exemplo, um floppy disk, um disco flexível, um disco rígido, uma fitamagnética, ou qualquer outro meio magnético, um CD-ROM, qualquer outromeio ótico, cartões perfurados, fita de papel, qualquer outro meio físico compadrões de furos, uma RAM, uma PROM, e uma EPROM, uma EPROM Ins-tantânea, qualquer outro chip ou cartucho de memória, uma onda portadoracomo aqui adiante descrita, ou qualquer outro meio do qual um computadorpossa ler.

Várias formas de meios legíveis por computador podem estarenvolvidas na execução de uma ou mais seqüências de uma ou mais instru-ções para o processador 1335 para execução. Por exemplo, as instruçõespodem inicialmente ser executadas em um disco magnético de um computa-dor remoto. O computador remoto pode carregar as instruções na sua me-mória dinâmica e enviar as instruções por uma linha telefônica utilizando ummodem. Um modem local para o sistema de computador 1300 pode receberos dados na linha telefônica e utilizar um transmissor infravermelho paraconverter os dados para um sinal infravermelho. Um detector infravermelhoacoplado na barra condutora 1345 pode receber os dados carregados nosinal infravermelho e colocar os dados sobre a barra condutora 1345. A bar-ra condutora 1345 carrega os dados para a memória principal 1320, da qualo processador 1335 recupera e executa as instruções. As instruções recebi-das pela memória principal 1320 podem opcionalmente ser armazenadas nodispositivo de armazenamento 1330 ou antes ou após a execução pelo pro-cessador 1335.

O sistema de computador 1300 também inclui uma interface decomunicação 1340 acoplada na barra condutora 1345. A interface de comu-nicação 1340 provê um acoplamento de comunicação de dados de duas viaspara uma conexão de rede 1375 que está conectada a uma rede local 1355.

Por exemplo, a interface de comunicação 1340 pode ser um cartão de rededigital de serviços integrados (ISDN) ou um modem para prover uma comu-nicação de dados para um tipo correspondente de linhas telefônicas. Comooutro exemplo, a interface de comunicação 1340 pode ser um cartão de redede área local (LAN) para prover uma conexão de comunicação de dadospara uma LAN compatível. Conexões sem fio podem também ser implemen-tadas. Em qualquer tal implementação, a interface de comunicação 1340envia e recebe sinais elétricos, eletromagnéticos ou óticos que carregam osfluxos de dados digitais que representam os vários tipos de informações.

A conexão de rede 1375 tipicamente provê uma comunicação dedados através de uma ou mais redes para outros serviços de dados. Porexemplo, a conexão de rede 1375 pode prover uma conexão através de umarede local 1355 para um computador hospedeiro 1350 ou para um equipa-mento de dados operado por um Provedor de Serviços de Internet (ISP)1365. O ISP 1365 por sua vez provê os serviços de comunicação de dadosatravés de uma rede de comunicação de dados de pacote ampla mundialcomumente referida como a "Internet" 1360. A rede local 1355 e a Internet1360 ambas utilizam sinais elétricos, eletromagnéticos ou óticos que carre-gam os fluxos de dados digitais. O sinal através das várias redes e os sinaissobre a conexão de rede 1375 e através da interface de comunicação 1340,a qual carrega os dados digitais para o e do sistema de computador 1300,são formas exemplares de ondas portadoras que transportam as informa-ções.

O sistema de computador 1300 pode enviar mensagens e rece-ber dados, que incluem o código de programa, através da(s) rede(s), da co-nexão de rede 1375 e da interface de comunicação 1340. No exemplo deInternet, um servidor 1370 pode transmitir o código solicitado para um pro-grama de aplicativo através da Internet 1360, do ISP 1365, da rede local1355 e da interface de comunicação 1340. De acordo com a invenção, talaplicativo carregado provê o processamento de imagens capturadas comoaqui descrito.

O código recebido pode ser executado pelo processador 1335,como este é recebido, e/ou armazenado no dispositivo de armazenamento1330, ou outro armazenamento não volátil para uma execução posterior.Deste modo, o sistema de computador 1300 pode obter o código de aplicati-vo na forma de uma onda portadora.

Claims (10)

1. Método para processar uma imagem capturada que compre-ende um documento de imagem formada, o dito método compreendendo:detectar as informações gráficas na imagem capturada relativasà transição entre o dito documento de imagem formada e o restante da ditaimagem capturada;selecionar uma ou mais linhas das ditas informações gráficasque correspondem às bordas do dito documento de imagem formada;calcular os cantos do dito documento de imagem formada combase na interseção de uma ou mais linhas que correspondem às bordas dodito documento de imagem formada;isolar o dito documento de imagem formada do fundo da ditaimagem capturada com base em uma ou mais linhas que correspondem àsbordas do dito documento de imagem formada;ajustar uma rede de coordenadas curvas sobre o dito documentode imagem formada;estirar a dita rede de coordenadas curvas para uma rede de co-ordenadas retangulares;ajustar a dita rede de coordenadas retangulares para uma redede coordenadas retangulares bem proporcionada.

2. Método de acordo com a reivindicação 1, ainda compreen-dendo as etapas de:mapear as coordenadas de pixels do dito documento de imagemformada para coordenadas que correspondem a uma perspectiva não distor-cida do dito documento de imagem formada com base no dito desvio compu-tado.

3. Método de acordo com a reivindicação 2, ainda compreen-dendo as etapas de:girar o dito documento de imagem formada não distorcido deacordo com a dita determinação de formato do dito documento de imagemformada não distorcido.

4. Sistema para processar uma imagem capturada, a dita ima-gem capturada compreendendo um documento de imagem formada, o ditosistema compreendendo:um meio para selecionar uma ou mais linhas das ditas informa-ções gráficas que correspondem às bordas do dito documento de imagemformada;um meio para calcular os cantos do dito documento de imagemformada com base na interseção de uma ou mais linhas que correspondemàs bordas do dito documento de imagem formada;um meio para isolar o dito documento de imagem formada dofundo da dita imagem capturada com base em uma ou mais linhas que cor-respondem às bordas do dito documento de imagem formada;um meio para ajustar uma rede de coordenadas curvas sobre odito documento de imagem formada;um meio para estirar a dita rede de coordenadas curvas parauma rede de coordenadas retangulares; eum meio para ajustar a dita rede de coordenadas retangularespara uma rede de coordenadas retangulares bem proporcionada.

5. Meio legível por computador para processar uma imagemcapturada, o meio legível por computador executando uma ou mais seqüên-cias de uma ou mais instruções as quais, quando executadas por um oumais processadores, fazem com que os um ou mais processadores execu-tem as etapas implementadas por computador de:detectar as informações gráficas na imagem capturada relativasà transição entre o dito documento de imagem formada e o restante da ditaimagem capturada;selecionar uma ou mais linhas das ditas informações gráficasque correspondem às bordas do dito documento de imagem formada;calcular os cantos do dito documento de imagem formada combase na interseção de uma ou mais linhas que correspondem às bordas dodito documento de imagem formada;isolar o dito documento de imagem formada do fundo da ditaimagem capturada com base em uma ou mais linhas que correspondem àsbordas do dito documento de imagem formada;ajustar uma rede de coordenadas curvas sobre o dito documentode imagem formada;estirar a dita rede de coordenadas curvas para uma rede de co-ordenadas retangulares;ajustar a dita rede de coordenadas retangulares para uma redede coordenadas retangulares bem proporcionada;reamostrar os pixels do dito documento de imagem formada combase nos ditos desvios computados.

6. Método de acordo com a reivindicação 5, ainda compreen-dendo as etapas de:mapear as coordenadas de pixels do dito documento de imagemformada para coordenadas que correspondem a uma perspectiva não distor-cida do dito documento de imagem formada com base no dito desvio compu-tado.

7. Método de acordo com a reivindicação 6, ainda compreen-dendo as etapas de:girar o dito documento de imagem formada não distorcido deacordo com a dita determinação de formato do dito documento de imagemformada não distorcido.

8. Método para processar uma imagem capturada que compre-ende um documento de imagem formada, o dito método compreendendo:separar as áreas de texto do restante da dita imagem capturada;melhorar a direção de linhas de texto nas ditas áreas de texto;extrair as ditas linhas de texto;selecionar uma função polinomial para ajustar as ditas linhas detexto.

9. Método de acordo com a reivindicação 8, em que a dita etapade melhoramento ainda compreende as etapas de:detectar a distância entre as ditas linhas de texto;comprimir a dita imagem capturada sob uma taxa de compressão;computar a direção para cada pixel nas ditas linhas de texto;eliminar os espaços entre os caracteres de modo que os carac-teres na mesma linha de texto conectem-se, mas os caracteres não namesma linha de texto fiquem separados.

10. Método de acordo com a reivindicação 9, em que a direçãode cada pixel no dito texto de linhas é determinada utilizando uma pluralida-de de gabaritos direcionais de 9x9, onde cada gabarito compreende um blo-co preto no centro que representa o pixel e oito blocos cinza que estendem-se do bloco preto que descrevem uma direção do pixel, e os valores de nível10 de cinza são somados para cada um da pluralidade de gabaritos direcionaispara determinar a direção do pixel.