Resources Contact Us Home
Browse by: INVENTOR PATENT HOLDER PATENT NUMBER DATE
 
 
Method of scanning a scene and corresponding scanning device
7583365 Method of scanning a scene and corresponding scanning device
Patent Drawings:Drawing: 7583365-2    Drawing: 7583365-3    Drawing: 7583365-4    Drawing: 7583365-5    Drawing: 7583365-6    Drawing: 7583365-7    Drawing: 7583365-8    
« 1 »

(7 images)

Inventor: Lepere, et al.
Date Issued: September 1, 2009
Application: 11/392,029
Filed: March 29, 2006
Inventors: Lepere; Gregory (Sevran, FR)
Souffez; Pascal (Paris, FR)
Assignee: Mensi, S.A. (Fontenay-Sous-Bois, FR)
Primary Examiner: Tarcza; Thomas H
Assistant Examiner: Ratcliffe; Luke D
Attorney Or Agent: Cooper & Dunham LLP
U.S. Class: 356/4.01
Field Of Search: 356/3.01; 356/4.01; 356/5.01; 356/6; 356/7; 356/8; 356/9; 356/10; 356/11; 356/12; 356/13; 356/14; 356/15; 356/16; 356/17; 356/18; 356/19; 356/20; 356/21; 356/22
International Class: G01C 3/08
U.S Patent Documents:
Foreign Patent Documents:
Other References:









Abstract: The present invention provides devices and methods for multi-dimensional scanning of a scene. In particular, this invention provides scanning devices and methods employing controllable light beam scanning devices capable of sending a light beam onto a scene, and of receiving corresponding light returned from the scene, and controllers capable of operating the scanning device at selected beam orientations, and of gaining distance information from the scanning device at the beam orientations. The controller can dynamically define beam orientations using the distance information gained from preceding beam orientations.
Claim: What is claimed is:

1. A method of scanning a scene, said method comprising: a. sending a light beam to the scene according to a beam orientation, and gaining distance information from thereturn of said light beam, b. selectively repeating step a. with a plurality of other beam orientations in one scanning of the scene, wherein step b. comprises: b1. after one or more repetitions of step a. in the one scanning, defining the next beamorientation using distance information gained at one or more preceding beam orientations of the one scanning, c. forming a first angular sector from the beam orientations of steps a. and b., d. selectively repeating steps a. and b. at further beamorientations, said further beam orientations forming a further angular sector derived from a selected portion of said first angular sector, with a lateral shift related to the angular deviations between the beam orientations in said portion of said firstangular sector, wherein step d. comprises: d1. determining angular domains within said first angular sector, each angular domain comprising beam orientations having distance information within a respective distance range, d2. selecting said portion ofsaid first angular sector from one or more angular domains having higher distance ranges, d3. defining said further angular sector from said portion, with a lateral shift derived from said higher distance ranges.

2. The method of claim 1, wherein step d. further comprises: d4. selectively repeating step d3., with the same portion of said first angular sector, and with a lateral shift being further increased in accordance with said higher distanceranges.

3. The method of claim 1, wherein step d. further comprises: d5. selecting a new portion of said first angular, sector from one or more angular domains having new distance ranges being lower than said higher distance ranges of step d2., andd6. defining a new further angular sector from said new portion, with a new lateral shift derived from said new distance ranges.

4. The method of claim 3, wherein step d. further comprises: d7. selectively repeating again step d3., with the same portion of said first angular sector, and with a lateral shift being further increased in accordance with said higher distanceranges.

5. The method of claim 3, wherein step d5. comprises including said higher distance ranges within said new distance ranges.
Description: BACKGROUND OF THE INVENTION

The present invention is concerned with multi-dimensional scanning of a scene.

In industrial production environments, most installations and machineries are built according to plans. However, those installations and machineries tend to require upgrading over time and/or are subject to additions which may or may not beappropriately documented.

For certain applications, such as offshore platforms for instance, it is necessary when adding an additional element to be sure that it will fit in the existing installation. Other applications include scanning existing permanent structures forupgrading and/or control when no plans are readily available.

Thus, methods and apparatuses have been proposed to try and obtain "as-built" plans of these structures. Most recently, solutions involving laser digitizing apparatuses have been proposed.

Practically, those solutions imply projecting a scanning laser beam on an installation being captured. At each laser orientation, the distance is derived from the time or the phase difference in the laser to-and-fro path to a reflecting point. After suitably scanning the scene, this results in a three-dimensional set of points, also referred to as "cloud of points", corresponding to the installation.

The scanning of the scene is usually performed as a method, which comprises: taking a picture of the scene, selecting a scene portion to be scanned and corresponding scanning information; scanning the scene portion according to the selectedscanning information.

When performing such a method, the desired scanning resolution defines the scanning time, and the size of the resulting data, and, accordingly, the needs in terms of hardware and software capabilities.

The applicant company has observed that this may not be entirely satisfactory in all circumstances, at it will be explained hereinafter in more details.

BRIEF SUMMARY OF THE INVENTION

The invention aims at improving the situation.

The invention proposes a method of scanning a scene, said method comprising: a. sending a light beam to the scene according to a beam orientation, and gaining distance information from the return of said light beam, b. selectively repeating stepa. with a plurality of other beam orientations, wherein step b. comprises b1. after one or more repetitions of step a., defining the next beam orientation using distance information gained at one or more preceding beam orientations.

Such a method of scanning a scene makes it possible to adjust the scanning resolution in order to better image the scene. This method enables having a substantially constant density of scan points in terms of space spread. This means thatscenes requiring a given resolution regardless of the difference in distance to the points being scanned can be acquired in a reduced time. The post-processing time is also consequently diminished since cloud resulting from the scanning contains lesspoints than a conventional method which would use constant resolution.

Such a method of scanning a scene makes it possible to recognize some interesting areas of the scene such as edges. Then, locally and when deemed appropriate, the scanning resolution may be adjusted in order to better image interesting detailsof the scene. The time of acquisition is thus minimized compared to a classic method, for a similar scanning quality. The post-processing time is also consequently diminished since cloud resulting from the scanning contains less points.

An scanning device, is also proposed, comprising: a controllable light beam scanning device capable of scanning a light beam onto a scene, and of receiving corresponding light returns from the scene, a controller capable of operating saidscanning device at selected beam orientations, and gaining distance information from said scanning device at said beam orientations, wherein the controller is further capable of dynamically defining a further beam orientation using distance informationgained at preceding beam orientations.

This invention also encompasses software code, adapted to execute the steps of the above method. It further encompasses software code, adapted to implement the controller of the above device.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THEDRAWINGS

Other alternative features and advantages of the invention will appear in the detailed description below and in the appending drawings, on which:

FIG. 1 shows a block diagram of an exemplary scanning device;

FIG. 2 shows an exemplary flowchart of a known method of scanning a scene;

FIG. 3 shows an exemplary flowchart of a method of scanning a scene;

FIG. 4 shows an exemplary detailed flowchart of part of the method of FIG. 3;

FIG. 5a and FIG. 5b show an exemplary detailed flowchart of another part of the method of FIG. 3;

FIG. 6 shows an exemplary detailed flowchart of part of the method of FIGS. 5a and 5b ;

FIG. 7 shows an exemplary flowchart of part of the method of FIG. 3

FIG. 8a shows an exemplary side view of a set of scanning paths and laser orientations used in the method of FIG. 7 ; and

FIG. 8b shows an exemplary top view of a set of scanning paths and laser orientations used in the method of FIG. 7.

These drawings form an integral part of the description of the present invention, and may serve by themselves to support features of the invention.

DETAILED DESCRIPTION OF THE INVENTION

Now, making reference to software entities imposes certain conventions in notation. For example, in the detailed description, the quote sign " and/or Italics may be used when deemed necessary for clarity, e.g. to distinguish between naturallanguage and a software entity. Generally: a software entity which starts with the symbol "$", is a variable, a data object or a data structure; it may be an array, or an equivalent data structure, if it terminates with a bracket expression, e.g.$Ang(k); a software entity which does not start with the symbol "$", but terminates with a bracket expression, e.g. Distance ( ), is generally a procedure or function optionally, a procedure or function may be called with one or more arguments(parameters) indicated within the round brackets, e.g. Distance($Ang(k)); undefined data are generally shown in italics.

Also, the references to functions, and the function names, are for convenience only. They do not imply the use of software code whose structure matches the functions as described hereinafter.

As seen on FIG. 1, a scene 2 is scanned by means of a controllable scanning laser device comprising a laser 4.

Laser 4 projects a beam 6 at a set of laser orientations, and, at each of those orientations, the distance to the scene is derived from the time or the phase difference between the beam 6 and a reflected beam 8.

The laser orientations may be transmitted to the laser 4 by a controller 10. Controller 10 may select those orientations according to a method which will be described further below.

Once scene 2 has been scanned, controller 10 may transmit the distances and laser orientations to a post processing unit 12. The post processing unit 12 may combine the distances with the laser orientations to define points of a cloud 14 ofpoints representing the scene 2.

FIG. 2 shows a known method of scanning a scene. This method comprises the following steps: PA1. initiating the laser orientation controlling program. PA2. initiating a scanning path currPath with a path 1st Path. PA3. scanning the pathcurrPath, i.e. measuring the distance to the scene at every laser orientation, each laser orientation being derived from the previous one according to the path currPath and the angle step. PA4. if there is a path left, repeating step PA3, else PA5. transmitting the data to the post processing unit 12.

This simple method will return a cloud, the level of details of which depends on the scanning resolution, i.e. the smaller the angle step, the higher the resolution.

Until now, a constant scanning resolution is being used. This means that a choice has to be made regarding the tradeoff level of details/scanning time, that is basically defined by the angular step between the orientations.

In scenes showing a large depth, this scanning resolution also leads to an uneven spatial resolution. By spatial resolution, the applicant refers to the average distance, in space, between the points that are scanned. As a consequence of aconstant scanning resolution, two scanned points in the depth of the scene are a lot more distant to each other than two scanned points close to the laser. In the scanning of a road or of a tunnel, this means that several scannings have to be performedto maintain constant spatial resolution over the scene.

Moreover, in certain applications, high level of details is required, and thus the scanning resolution has to be as high as possible. This means that a scene presenting several important details, but mostly uniform for the rest, is scanned witha maximum resolution, although it is unnecessary for most of the scene. This represents a waste of time and resources.

Further, when an excessive resolution is used, the cloud of points obtained contains a lot of "useless" points. This either tends to slow down the post-processing of the cloud, or necessitates a preliminary step for cleaning out redundant databefore the post-processing.

Thus, not only do classic methods take unnecessary time for acquiring the cloud, but they also lengthen its post-processing.

In general the paths are scanned from bottom to ceiling, that is the paths are vertical, and start from the ground (or a given angle) on up. Other embodiments are possible.

Assume that a given angular step is being used. Then, considering two consecutive laser orientations on the laser scanning path, the corresponding laser beams will hit two different points of the scene, and the actual spacing between these twopoints is related to the angular resolution and to their distances to the laser source.

If those two points belong to a surface substantially orthogonal to the direction of the laser beam, then the difference in the distance gained at those points will be rather small, and other points gained on this surface will all be at a givendistance from each other.

However, if the surface is somewhat parallel with the laser direction, i.e. shows some depth, then the distance between points gained on this surface will substantially grow as "deeper" points are scanned. This means for instance that a roadbeing scanned will show a lot of points close to the scanning device and then will progressively capture less and less points as the scanning is performed on further points.

The applicant has concluded that a better overall quality may be reached by predicting where a next scanning point may be in order to reach a substantially constant spatial resolution, and by deducing the orientation for scanning this point fromthe previous ones.

The applicant has also observed that, in some situations, the respective laser returns at two laser orientations will show significantly different distances to the scene. This is called here a "discontinuity" in a part of the scene, as observed. In fact, a discontinuity will be associated to the two or more laser orientations at which it is detected, and/or to a portion or segment of the scanning path which encompasses the said two or more laser orientations.

The applicant has concluded that a better spatial resolution may be desired where such differences in distance or "discontinuities" are met. This makes it possible to detect edges of portions of a scene, as well as other interesting points ofthis scene, such as curvature zones.

Thus, the whole scene may be scanned with an attempted "average" resolution, corresponding to a desired spatial resolution for the scene. Then, a better resolution may be used where "discontinuities" are detected. The search for discontinuitiesis used extensively in the methods described below. It allows to ameliorate the spatial resolution repartition.

The applicant thus proposes a new method of scanning wherein the scanning is organized in scan lines or scan paths, at a lateral angular deviation from each other.

FIG. 3 shows an exemplary flowchart of a first method of scanning a scene. It may comprise the following operations: M1. an initialization operation in which scanning parameters may be set as mentioned above, e.g. the spatial scanningresolution searched for and a first path. M2. a variable currPath which designates a scanning path may be initiated. It may contain data representing the first path determined in operation M1. M3. a variable currPoint it may be initiated. It maycontain data representing the first a point of currPath aimed at by the laser at a starting orientation. M4. a function Distance( ) may use the laser orientation defining currPoint as an argument and determine the distance from the laser to the scene,to define a scanning point. M5. the next point may be calculated from the preceding point(s), that is from the orientations of the laser and the corresponding scanning points. A beam orientation is thus obtained, which is supposed to aim at a point ata distance from its neighbors in correspondence with the spacing resolution. M6. the calculated beam orientation may be checked for validity.

If the calculated beam orientation is within the scene, steps M4 to M6 may be repeated with further calculated laser orientations.

Else, M7. a scanning path has been scanned, and it may be analyzed with a function Path_Review( ), which will be explained in more detail further below. M8. a check may be made to see if there is a scanning path not yet scanned.

If so, variable currPath may be updated with data representing this path, according to a method which will be described in more detail below, and the scanning may be repeated with operation M3, with the new value of currPath.

Else, M9. the results may be transmitted to the post processing unit 12.

As apparent from this flowchart, this method comprises two loops intertwined: a "local" loop scans the scene along a scanning path, by calculating beam orientations from previously obtained data, in order to reach a given spatial resolution, andmay further improve the results with a review. a "global" loop selectively repeats the local loop until there are no more paths for the scanning of the scene.

Loops and functions of this method will be described in more detail with FIGS. 4 to 7.

FIG. 4 shows an exemplary flowchart of a part of FIG. 3. More precisely, it may detail operations M3 through M6, i.e. the "local" loop, prior to the review step.

This exemplary implementation of those operations may comprise the following operations: M31. scanning parameters may be obtained, including index k set to 0 and a variable $ang_init which corresponds to the first orientation of the path. M32. a first laser orientation $Ang(0) or $Ang(k) with k=0 may be initiated. M41. a distance $D(k) for the k-th laser orientation may be set as the result of a function Distance( ). This function may use the laser orientation $Ang(k) as an argument,project the laser beam on the scene at an angle equal to $Ang(k) from the origin point of the scanning path, and return the measured distance to the scene as described earlier. M51. index k may be increased. M52. index k may be evaluated.

If k.ltoreq.3, M53. the laser orientation $Ang(k) for the k-th laser orientation may be set as the result of a function Step_init( ). This function may calculate an angular step from the sought for spatial resolution and the distancesavailable, namely $D(0) to $D(2) and add that step to $Ang(k-1) .

Else, M54. the laser orientation $Ang(k) for the k-th laser orientation may be set as the result of a function Step(k). This function may perform a regression on the points deducted from the respective distances $D(k-3) to $D(k-1), andcalculate a projected point. An orientation may then be calculated to aim at this projected point and be returned to define $Ang(k). M61. a function End_Path( ) may be executed, which checks whether $Ang(k) calculated at step M54 is within thescanning range or not.

If yes, then steps M41 to M61 are repeated with this orientation.

Else, the method proceeds to B, which is the starting point of the function Path_Review( ).

A variety of solutions may be implemented to calculate the next beam orientation from the prior ones. While the preferred embodiment uses two separate functions, a unique function could be used.

Alternative methods for calculating the next beam orientation may include using higher degree regressions, splines, or other suitable methods of calculation. Some alternative methods may predict the next beam orientation directly from the gaineddistances, rather than extrapolations on the differences between distances gained at neighboring beam orientations.

Function Path_Review( ) may comprise two separate sub-functions represented on FIGS. 5a and 5b, which are here operated simultaneously. They may however be operated sequentially.

FIG. 5a shows a method for detecting discontinuities in the path that has been scanned, and for scanning those discontinuities. It may comprise the following steps: PRD1. a check for a discontinuity may be performed by comparing the k-thdistance $D(k) to the scene to the (k-1)-th distance $D(k-1). If this difference is small enough, e.g, inferior to a condition value $Cond, no discontinuity is detected. This difference may be seen as the local derivative of the distance to the scenealong the path, and value $Cond as a lower limit to eliminate distance noise. It means that successive points are close enough to each other with respect to the global resolution. When the difference exceeds $Cond, it indicates that the laserorientations corresponding respectively to index k-1 and index k correspond to points located at a significant distance of each other.

If a discontinuity is not detected, an operation PRD2 may be performed to decrease index k.

Else, PRD3. an angle step $Step may be defined as the result the tenth of the angular difference between $Ang(k) and $Ang(k-1). PRD4. a function Scan( ) may be performed. Function Scan( ) may use k and $Step as arguments. Function Scan( )may perform a linear scan between the beam orientations $Ang(k) and $Ang(k-1), using $Step as an angular step. Function Scan( ) will be described hereinafter. PRD5. index k is checked to see whether the whole scanning path has been reviewed.

If yes, PRD6. the next path is defined according to the method of FIG. 7.

Else, step PRD2 is executed to decrease index k, and steps PRD1 to PRD5 are repeated.

FIG. 5b shows a method for detecting curvature zones in the path that has been scanned, and for scanning those curvature zones. It may comprise the following steps: PRC1. a check for a curvature zone may be performed by comparing the curvatureshown at the k-th orientation to a given condition $Cond2. Thus curvature may be calculated from a function Curv( ), which may use k as an argument and return the curvature shown by the points corresponding to the distances $D(k) to $D(k-2). If thisdifference is small enough, e.g, inferior to the condition value $Cond2, no curvature zone is detected. Condition value $Cond2 ensures that scanned point correspond to the global resolution sought for. When the difference exceeds $Cond2, it indicatesthat the laser orientations corresponding respectively to index k-2 to index k correspond to points located at a significant distance of each other.

If a discontinuity is not detected, an operation PRC2 may be performed to decrease index k.

Else, PRC3. an angle step $Step may be defined as the result the twentieth of the angular difference between $Ang(k) and $Ang(k-2). PRC4. a function Scan( ) may be performed. a function Scan( ) may be performed. Function Scan( ) may use k, 2and $Step as arguments. Function Scan( ) may perform a linear scan between the beam orientations $Ang(k) and $Ang(k-2), using $Step as an angular step. Function Scan( ) will be described hereinafter. PRC5. index k is checked to see whether the wholescanning path has been reviewed.

If yes, PRC6. the next path is defined according to the method of FIG. 7.

Else, step PRC2 is executed to decrease index k, and steps PRC1 to PRC5 are repeated.

Some differences between the method of FIG. 5a and that of FIG. 5b may be noted: in the method of FIG. 5a, a discontinuity is searched, which relates to steep changes in terms of direct distance between the scanned points, which allows to easilydetect depth changes in the scanning; in the method of FIG. 5b, a curvature zone is searched, which relates to the curvature shown by the scanned points, which allows to easily detect holes or bumps or other such irregularities in the shape of the scene.

The methods of FIG. 5a and 5b may be run simultaneously, sequentially or separately. When run simultaneously or sequentially, the results of one of those methods may be used for the other method, e.g. function Scan( ) will not be run twicebetween two given orientations. Those methods could also be implemented differently, in order to take into account more orientations than shown here, to better detection.

FIG. 6 shows a simple implementation of function Scan( ). This function may comprise the following operations: S1. receiving parameters k, n, and $Step, which respectively indicate the orientations between which the linear scan is to beperformed, and the resolution of this scan. S2. defining an index j=1. S3. defining a temporary orientation $Ang_tmp from $Ang(k) minus j times $Step. S4. using function Distance( ) to define a distance $E(j) from the temporary orientation$Ang_temp. S5. index j may be checked to see whether all the orientations between $Ang(k) and $Ang(k-n) have been scanned.

If yes, S6. distances $E(j) are returned.

Else, S7. index j is increased, and steps S2 to S5 are repeated.

As can be seen from this figure, function Scan( ) is a function which scans at orientations between $Ang(k) and $Ang(k-n) at a linear resolution $Step.

Once the first full range has been scanned with the method described above, the following ranges are partly deduced from this scanning according to the method of FIG. 7, and individually scanned using the same method as the first full range.

As seen on FIG. 7, after step M7 has been performed on the first full range, the following operations may be performed to scan the rest of the scene: L1. the obtained distances, i.e. $D(k) for those gained on the first pass and $E(j) for thosegained during the path review may be classified in domains. More precisely, the first scanning path comprises points deduced from the distances gained at respective laser orientations. Those orientations form a first angular sector. Thus, the firstangular sector may be divided in angular domains, each comprising at least one or more angular sectors containing beam orientations associated with similar distances. A given number of angular domains may thus be chosen to divide said first angularsector, wherein all distances gained about an angular sector of a given angular domain is within a given distance range. An example of the association of angular domains with respective distance ranges will be more apparent from FIG. 8a, which will bedescribed further below. L2. a lateral step may be deduced for each domain. This lateral step may represent an average angular step separating the orientations comprised in each domain. This lateral step will be used in much the same way the"predicted orientation" is used above. That is it represents a lateral deviation estimated for the orientations of each domain. While an average of the angular differences of successive orientations within each domain may be contemplated to calculatethe lateral step, other formulas may be used, namely based on the distances associated with the orientations of each domain. L3. the next path to be scanned may then be set. To do so, the domain having the highest distance range is selected,representing a portion of the first angular sector. This domain is then shifted laterally with an angular deviation equal to the lateral step of this domain, and the next path currPath is defined as this further angular sector. L4. at this point, thepath currPath is shifted by a global lateral deviation with respect to the first angular sector. Domains having lateral steps that are close to the global lateral deviation may then be added to the path currPath. That is, those domains may be shiftedlaterally with an angular deviation equal to the global lateral deviation, and included in the definition of currPath. L5. path currPath may then be scanned and reviewed according to the above described method. L6. according to the results of thescanning of path currPath, the domains may then be updated. Namely, the update of a domain may consist in rearranging angular sectors within a domain which show distances higher than the distance range of their current domain. A comparison may also beperformed with the previous paths, in order to reveal discrepancies. Those discrepancies may be for instance the discovery of a distance that substantially exceeds the distances of the highest distance range, or other discrepancies identified by the manskilled in the art. Where such a discrepancy is found, a full range scanning may be performed, at a lateral deviation equal to the global deviation from the first angular sector, and a domain update may follow this full range scanning.

After the domain update is done, steps L3 to L6 may be repeated until the last path of the scene has been scanned. Typically, if a given domain has lateral step comprised between two multiples of the lateral step of domains having a higherdistance range, path currPath may be defined as this given domain, shifted laterally by a deviation equal to the lateral step of this given domain. The scanning of path currPath is then performed independently, between the respective scanning of the twodomains having a higher distance range.

The methods described above enable fast and accurate scanning of a scene. In the examples described, those paths are generally sensibly vertical.

To illustrate the method of FIG. 7, an exemplary scanning is shown on FIGS. 8a and 8b. FIG. 8a is a side view of a scene scanned according to this method, and FIG. 8b a side view of the same scene.

On these figures, a plurality of paths P1, P1m, P1h, P2, P2h, P3h and P4h are shown. Path P1 is a full range scanning, and shows three domains D1h, D1m and D1l. Domain D1h has the highest distance range (the extremity of which is not shown onFIG. 8b, but is visible on FIG. 8a), domain D1l has the lowest distance range, and domain D1m has a distance range in the middle of the above. On FIGS. 8a and 8b, the distance ranges relative to each domain are made apparent by means of dotted arcuateportions.

Paths P2h, P3h and P4h, which are substantially parallel and at a distance .DELTA.h of each other, represent domain D1h shifted laterally by an angular deviation equal to its lateral step, namely .DELTA.Ph.

Path P1m is analogous to path P1h, with domain D1m, step .DELTA.m and lateral step .DELTA.Pm in lieu of domain D1h, step .DELTA.h and lateral step .DELTA.Ph. As the scanning is carried on, there would also be a path P1l associated to a distance.DELTA.l and a lateral step .DELTA.Pl. However, this path is not shown in order to facilitate the understanding of this example.

Path P2 represents another full range scanning, due to a discontinuity, which will described in further detail below.

The method of FIG. 7 may be executed as follows: path P1 is scanned and reviewed according to the methods of FIGS. 4 to 6; the resulting distances are classified in the three domains D1h, D1m and D1l and corresponding lateral steps .DELTA.h,.DELTA.m and .DELTA.l may be calculated; path P1h is defined from domain D1h, and scanned and reviewed according to the methods of FIGS. 4 to 6; domains D1h, D1m and D1l are updated, without change since no orientation within path P1h shows a difference;path P2h is scanned and reviewed like path P1h; path P3h is then supposed to be scanned. However, adjoining path P1m is scanned and reviewed simultaneously in order to increase the scanning speed. This simultaneous scanning is optional and both pathsP3h and P1m could be scanned separately; path P4h is scanned and reviewed like path P2h; during the update of the domains following the review of path P4h, a discrepancy is detected. In the example shown, the discrepancy in path P4h is a "hole" in thebackground of the scene, which returns no measure. accordingly, a full range scanning is performed on path P2, which corresponds to path P1 shifted laterally by a deviation equal to that of path P4h; after the scan of path P2, domains are updated. Inthe example shown, the full range scanning of path P2 has shown that the discrepancy found in path P4h is a hole. This means there is no need for a new definition of the domains, and thus the domains remain unchanged; and the scanning of the rest of thescene is performed in the same way until the side end of the scene is reached.

For a better understanding of the domains, table 1 below shows exemplary distances gained about the paths of FIG. 8a and 8b.

As appears in this table, domains D1l, D1m and D1h have been defined such that:

D1l={Positions where the measured distance is comprised in [0 m; 1 m[ }

D1m={Positions where the measured distance is comprised in [1 m; 3 m[ }

D1h={Positions where the measured distance is comprised in [3 m; 10 m[ }

TABLE-US-00001 P1 P1h . . . P3h + P1m P4h P2 .theta. Distance Domain Distance Domain . . . Distance Domain Distance Domain Distance Domain .theta..sub.1 2.9 D1m X X . . . 2.8 D1m X X 2.8 D1m .theta..sub.2 3.5 D1h 3.4 D1h . . . 3.2 D1h 3.1D1h 3.1 D1h .theta..sub.3 4 D1h 3.9 D1h . . . 3.7 D1h 3.6 D1h 3.6 D1h .theta..sub.4 5 D1h 4.9 D1h . . . 4.7 D1h ? ? ? D1h .theta..sub.5 6 D1h 5.9 D1h . . . 5.7 D1h ? ? ? D1h .theta..sub.6 8 D1h 7.9 D1h . . . 7.7 D1h 7.6 D1h 7.6 D1h .theta..sub.7 8D1h 7.9 D1h . . . 7.7 D1h 7.6 D1h 7.6 D1h .theta..sub.8 2.5 D1m X X . . . 2.4 D1m X X 2.4 D1m .theta..sub.9 1.5 D1m X X . . . 1.4 D1m X X 1.4 D1m .theta..sub.10 0.5 D1l X X . . . X X X X 0.5 D1l

It is clear from table 1 that angular positions of a given domain are not necessarily neighboring positions. For instance, domain D1m comprises three angular positions, .theta.1, .theta.8 and .theta.9.

Table 1 also shows how a given scanning path contains only distances measured at positions within the domain it concerns. The classification of the results for the update of the domains is further shown, along with the case of a discrepancy withthe full range scanning of path P2.

The choice to integrate all or part of the embodiment being described hereinbefore may depend upon the capabilities of the scanning light source and/or of the hardware/software assembly processing the light returns.

The example described herein is to be interpreted in a non restrictive manner, and the scope of the invention encompasses all alternatives accessible to those skilled in the art.

A variety of alternative embodiments may be contemplated: it would also be possible to monitor the distances gained along the paths, so that part of the reviewing step may be done while scanning, and the scanning part of the reviewing step beoperated as soon as possible, the distances of corresponding laser orientations along two consecutive paths could also be compared. This comparison could be used to detect "transverse" discontinuities, i.e. discontinuities in a direction transverse tothat of the paths. These discontinuities could be scanned to offer an even better image quality.

As mentioned above, the paths are generally vertical, and start from the ground (or a given angle) on up. However, the paths could start from ceiling (or a given angle) on down. They could also be generally horizontal and start from left toright or from right to left. Furthermore, the method and device described herein make use of a laser to calculate the distances. However, any light beam offering comparable precision and/or measurability could be used.

The above described method is implemented by software code. The controller in the above described example comprises software code. However, it could also be implemented as on-board circuitry, at least partially, by means of an FPGA circuitry orof an ASIC circuitry for instance.

This invention also covers the corresponding software code itself, especially when made available on any appropriate computer-readable medium. The expression "computer-readable medium" includes a storage medium such as magnetic or optic, as wellas a transmission medium such as a digital or analog signal. In the present case, the software code may basically include the "matching function", and/or the "controller", as well as code adapted to perform the same functions, while relying onappropriate middleware.

* * * * *
 
 
  Recently Added Patents
Cross-platform cloud-based map creation
Carrier for developing electrostatic charge image, developer for developing electrostatic charge image, image forming apparatus, and image forming method
Document layout method
Methods for integrating the production of cellulose nanofibrils with the production of cellulose nanocrystals
Opportunistic modem
Entropy encoding and decoding using direct level and run-length/level context-adaptive arithmetic coding/decoding modes
Phone messaging using audio streams
  Randomly Featured Patents
Access control system for information services based on a hardware and software signature of a requesting device
Doll
Travel blanket with arm support
Method and apparatus for providing an integrated membrane switch and capacitive sensor
Dynamic augmentation, reduction, and/or replacement of security information by evaluating logical expressions
Device for measuring the amount of flow and/or the speed of flow of a medium
Dioxetanes for use in assays
Pivotable support and heat sink apparatus removably connectable without tools to a computer processor
Measuring cups
Input device having indicating lamp