Segmentation of a postal object digital image by hough transform

The invention relates to a method of processing a digital image of a postal object with a view to automatically reading a postal address on said object by applying an automatic address recognition algorithm to said image.

Such a method is more particularly intended for the automatic reading of postal address on postal packets in a process of automatic sorting of postal packets. The automatic reading of addresses on postal objects of the letter type is conventionally carried out by conveying each letter on edge to pass it in front of a camera so as to capture a digital image of the letter which can then be binarized and filtered. Generally, the lines of characters constituting a postal address to be automatically read on a letter are arranged parallel to the foot of the letter or perpendicular to it, that is to say parallel to an edge of the image, so that a Automatic address recognition algorithm can be applied directly to a rectangular part of the digital image by decoding the characters in the image along the direction given by an edge of the image.

Postal items of the package type are generally bulky items which are conveyed flat on a belt. With this type of conveyor and this type of postal object, it is no longer possible to automatically read a postal address in a digital image of a package based on a privileged direction of the address lines provided by a predetermined reference. in the picture.

The aim of the invention is to provide a solution to the problem of processing digital images of postal packets with a view to automatically reading a postal address on each packet.

To this end, the invention relates to a method of processing a digital image of a postal object with a view to automatically reading a postal address on said object by applying an automatic address recognition algorithm on said image. , characterized in that it consists in dividing the image into image blocks of identical size, in applying to each image block a processing based on a Hough transformation in order to identify in the image block considered a privileged direction of the distribution of the image points in said block considered, in grouping contiguous image blocks in the image and having a common privileged direction in order to define a rectangular zone of interest in which is inscribed the grouping of said contiguous blocks having a common privileged direction such that this rectangular zone of interest has a longitudinal edge parallel to said common preferred direction, and applying the automatic address recognition algorithm to said area of ​​interest of the image in order to automatically read a postal address.

With this process, a rectangular area of ​​interest is obtained which extends longitudinally parallel to the character lines of a postal address so that it is possible by following the longitudinal edge of this area of ​​interest to apply an automatic recognition algorithm d 'addresses on the part of the digital image corresponding to this area of ​​interest even if the lines of the postal addresses in the digital image are not oriented along an edge of the digital image as is the case for a postal item of the letter type.

An example of implementation of the method according to the invention is described in more detail and illustrated by the accompanying drawings.

FIG. 1 is a simplified flowchart which illustrates the steps of the method according to the invention.

Figure 2 is a schematic representation of a digital image of a package including a mailing address.

FIG. 3 is a schematic representation of the image of a packet of FIG. 2 but partitioned into image blocks constituting thumbnails.

Figure 4 is a schematic representation of a group of thumbnails containing the mailing address information of the package of Figure 2.

Figure 5 is a schematic representation of the area of ​​interest of the image of Figure 2 which is formed from the group of thumbnails of Figure 4.

Figure 6 illustrates the principle of the Hough transformation on a thumbnail.

FIG. 1 very schematically illustrates in the form of a flowchart part of a postal packet sorting process including steps of digital image processing of the packets with a view to automatically reading an address from each postal packet. which will be used in the sorting process to automatically direct the package in question to a corresponding sorting outlet.

At 10, a package conveyed flat on a moving belt passes under a camera which captures a digital image of the package. Referring to the figure in which there is schematically represented an IP digital image of a packet comprising a postal address AP, it can be noted that in this image, the lines of the postal address AP are not written along lines parallel to the edge of the image. In general, such a digital image has been the subject of operations such as binarization, removal of isolated black pixels, such operations being intended to reduce the size of the corresponding computer file and to remove the parasitic and unnecessary data appearing. in the initial image. Thus, this image, which was initially defined by pixels in shades of gray, will be reduced to black or white points, these points being able to symbolize, depending on the type of processing, a pixel, a grouping of pixels, or even any other reduction of the pixels. of the initial image. In this way, the initial image could for example be reduced to a series of coordinates, each pair of coordinates defining a black point of the image.

According to the method of the invention, in step 20, the digital IP image (binarized and filtered) is divided or partitioned into identical image blocks called hereinafter images. Referring to Figure 3, there is shown the image of Figure 1 partitioned into 72 IT thumbnails, each thumbnail being square.

The objective of this partitioning step is to identify in each thumbnail, in a privileged direction of the distribution of the points of black color in each thumbnail. More particularly, the privileged direction of an thumbnail corresponds to the direction of one or more lines on which characters are written in the thumbnail, and this privileged direction will be identified by applying an algorithm to each thumbnail. For the result of the application of this algorithm to be relevant, it is important that the size of the thumbnails corresponds approximately to the size of a word, or to the size of several characters. Concretely, the thumbnails could for example be squares of 2cm by 2cm on the package. An identification algorithm in a thumbnail of a privileged direction will be presented and detailed below. Thus, at the end of step 30, a preferred direction is known for each thumbnail, which generally corresponds to the direction of lines of characters in the thumbnail, or to a direction perpendicular to these lines.

At 40, one or more groups of thumbnails are produced according to the criterion that the preferred directions of the thumbnails of a group are substantially parallel or substantially perpendicular, and that these thumbnails are contiguous. In FIG. 4, the group of thumbnails G1 which has been identified with the method according to the invention has been represented in the IP image. As can be seen, this group of thumbnails includes the AP address, but has not yet been formatted as a rectangle.

At 50, the areas of interest associated with each group of thumbnails from step 40 are produced. For a group of thumbnails, we will first calculate the most common or common preferred direction among the thumbnails of this group and associate this privileged direction to the group of thumbnails, then calculate the smaller rectangle including all the thumbnails of the group of thumbnails and having an edge parallel to the preferred direction of the group of thumbnails, so as to determine the area of ​​interest corresponding to the group of thumbnails considered. Referring to Figures 4 and 5, we can see the area of ​​interest ZI which has been established from the IP image, and which includes the recipient address written along lines parallel to the lower edge of the rectangle formed by the zone of interest ZI. More particularly, FIG. 5 is a representation of the zone of interest ZI, as it was extracted from the digital IP image, with the method according to the invention at step 50.

The zone or zones of interest identified at 50 will then be examined at 60 by an automatic character recognition algorithm, according to the privileged direction associated with each zone of interest, in order to extract from the packet the postal address sought.

An algorithm for detecting in a thumbnail of a privileged direction, as used in 30, could begin by applying to this thumbnail a polar Hough transformation. The Hough transformation, which is described in detail in “B. YU & AKJAIN Robust on fast squew detection algorithm for generic documents, Pattern Recognition Vol 29 n ° 10, page 1609 ”, allows to establish a polar table, from a thumbnail, this polar table giving for a certain number of lines on the thumbnail, the number of black dots contained in each of these lines. In such a polar array which has two inputs (r, 0), each pair (r, 0) corresponds to a line D (r, 0), the value of the polar array for a particular pair (r, 0) corresponding to the number of black dots contained in the line D (r, 0). In figure 6 we have represented an IT thumbnail which is a square with side C, in which we can see that the line D (r, 0) containing the black point N (x, y) is the line which passes through the point P (r, ©), and which is perpendicular to the vector ΟΡ (γ, Θ), O denoting the origin of a coordinate system associated with the thumbnail. More particularly, the vector OP (r, 0) is a vector having for modulus r, and for polar angle Θ. For a square image, on side C, provided with a mark centered on the lower left vertex of the image, the set of lines intercepting this square image is included in the set of lines D (r, ©) verifying - C <r <C.V2 and 0 ° <© <180 °.

Thus, in an image of 2cm by 2cm, as represented in figure 6, for which we decide to discretize the data in steps of 2mm for the radii, and in steps of 10 ° for the angles, we can build a polar table having 24 columns, each column corresponding to a radius value, and 18 rows, each row corresponding to an angular value. This array, which will be initialized so as to be equal to 0 for all the pairs (r, ©), will then be progressively filled, from each black point N (x, y) of the thumbnail, with the relation r = x. cos (©) + y.sin (©) (*):

For a black point N (x, y), we will calculate the value taken by r for 6 = 0 ° (with the relation (*)), we will round this value of r to the nearest 2mm, in accordance with the chosen discretization, to form a couple (r (0 °), 0 °). Then we will add 1 in the coordinate box (r (0 °), 0 °) of the polar table of the thumbnail. This operation must then be carried out for Θ = 10 °, 20 °, 30 ° ... 170 °.

This series of operations will have to be carried out for each black point included in the thumbnail to constitute the polar table of the thumbnail. The polar table thus obtained then gives for each pair (r, ©), the number of black points included in the line D (r, 6), this line being in this case a band 2mm wide, taking into account the discretization chosen.

To extract from this polar table the corresponding privileged direction of the thumbnail, we will calculate for each angle Θ the sum s²(©), which is the sum of the squares of the terms of the whole row of the polar table, then choose the angle Θ for which s²(©) is maximum.

The angle a corresponding to the privileged direction of the thumbnail is then worth a = © + 90 °. Indeed, if for example such an image consists of two black dots aligned along a straight line oriented at 120 °, we have²(30°) = 2² = 4, and s²(0) = 1²+1² = 2 for θ φ 30 °, and consequently, the privileged direction provided by the application of this algorithm to this thumbnail will be a = 120 °.

As we can see, an algorithm based on the transformation of Hough is efficient to detect a privileged direction of the distribution of the points in an image, but does not provide data on the location of the points of the image, which is insufficient. to identify 5 areas of interest in the image of a postal package. By partitioning the image into thumbnails according to the method of the invention, before applying such an algorithm to each thumbnail, an analysis of the image is obtained which provides sufficient information to constitute areas of interest which can be quickly exploited by an automatic address recognition algorithm.