Abstract:
Motorized machinery, such as overhead cranes, are widely used in industries all over the world. It is not easy to move crane payloads without oscillation, increasing the likelihood of obstacle collisions and other accidents. One possible solution to such problems could be aiding the operator with a dynamic map of the workspace that shows the current position of obstacles. This method discloses the use of a camera to take images of the workspace, using imaging blurring to smooth the obtained images, and drawing contours to produce an individual, near real-time map of the workspace. In one or more embodiments, known obstacles may be tagged in a manner which is readable by the camera. This image and historical images of the same workspace are layered on top of one another to produce a map of obstacles on the workspace floor. This imaging and layering can produce a near real-time map of obstacles that can be used to guide heavy motorized machinery around a workspace without incident.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims priority to U.S. Provisional Patent Application No. 62/066,642, entitled “Method For Near-Realtime Workspace Mapping,” which was filed on Oct. 21, 2014. 
     
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0002]    Not Applicable. 
       REFERENCE TO A “SEQUENCE LISTING,” A TABLE, OR A COMPUTER PROGRAM 
       [0003]    Not Applicable. 
     
    
     
       DESCRIPTION OF THE DRAWINGS 
         [0004]    The drawings constitute a part of this specification and include exemplary embodiments of the Method For Near-Realtime Workspace Mapping, which may be embodied in various forms. It is to be understood that in some instances, various aspects of the invention may be shown exaggerated or enlarged to facilitate an understanding of the invention. Therefore the drawings may not be to scale. 
           [0005]      FIG. 1  depicts a flowchart of one embodiment of the disclosed method, describing the process of mapping obstacles within a machine&#39;s workspace. 
           [0006]      FIG. 2  is an example of an image acquisition process wherein the workspace is divided into segments or regions such that multiple pictures can be taken and stitched together if desired to form one map. 
           [0007]      FIG. 3  depicts a processed image of the workspace that has been thresholded to create an image of workspace obstacles. In this Figure, the background is marked in grey, the foreground is marked in white, and the rest of the image is black. 
           [0008]      FIG. 4  depicts the processed image of the workspace that has been segmented, and the contours of such obstacles are extracted from the segmented image. 
           [0009]      FIG. 5  depicts three individual process image maps of the workplace at times T N , T N   _   1 , and T N   _   2 . 
           [0010]      FIG. 6  depicts an example map resulting from the disclosed method in which the three maps from  FIG. 5  have been overlaid wherein the hue or intensity suggests the higher probability of finding an obstacle in a location. 
           [0011]      FIG. 7  depicts a flowchart of one embodiment of the disclosed method, describing the process of mapping obstacles within a machine&#39;s workspace using tagged obstacles. 
           [0012]      FIG. 8  shows a representative example of how the angle of the reading on the tag by the camera can be used to determine the location of the tagged obstacle. 
       
    
    
     BACKGROUND OF THE INVENTION 
     Field of the Invention 
       [0013]    The subject matter of the present invention generally relates to machine operation safety. More particularly, the present invention relates to using mapping techniques to avoid overhead crane collisions and accidents. 
       Background 
       [0014]    Overhead cranes are widely used in industries all over the world. In many overhead cranes, the payload is suspended from a trolley that moves along a bridge. In some, the bridge itself can also move, enabling the crane to serve a large area. Due to their wide use throughout multiple industries, accidents in overhead crane operation remain a problem, causing damage and injuries. According to Crane Inspection and Certification Bureau, 90% of all crane accidents occur due to human error. Half of U.S. crane accidents that had injuries in 2009 resulted in fatalities. It is not easy to move crane payloads without oscillation, increasing the likelihood of obstacle collisions and other accidents. Some reasons for these incidents are limitations of the operator&#39;s field of view, depth perception, knowledge of the workspace, and the dynamic environment of the workspace. 
         [0015]    Control techniques like input shaping have been used to reduce the probability of crane collisions with obstacles. However, numerous factors, such as lack of knowledge of the workspace and common limitations in human perception of distance and depth, still limit the ability of the operator to safely move a crane through a workspace. Certain companies have tried to limit accidents by employing virtual boundaries around obstacles in the crane workplace; however, such boundaries typically have to be manually entered through a programming interface or a series of offline obstacle identification steps. 
         [0016]    Research has been conducted to model the workspace in order to avoid crushing obstacles during operations of heavy equipment. In addition, vision systems have been used for mapping and navigation for mobile robots and developing augmented reality workspaces. Simultaneous Localization and Mapping (SLAM) is a well-established method for mapping an unknown environment, or updating a map within a known environment by mobile robots and autonomous vehicles while at the same time keeping track of their current locations. Machine vision systems have also been implemented on tower cranes to help the operator see the workspace clearly. Some researchers have used machine vision as a means of measuring the crane hook location for feedback control, and some have conducted research into crane control for obstacle avoidance. However, in this work, there was no attempt to map the crane workspace. 
         [0017]    A solution to the aforementioned limitations is aiding the operator with a map of the workspace that depicts the current position of obstacles for use in crane operation. The map could be extended to include information about past locations of obstacles as well. The past locations could be an indication of the possibility of finding an obstacle at a given location in the workspace. This map could later be used to create virtual boundaries around the obstacle locations indicated by the map, actively preventing the collision between payload and obstacles. This method describes a novel approach of mapping the crane workspace in near-realtime using machine vision. 
       DETAILED DESCRIPTION OF THE INVENTION 
       [0018]    The subject matter of the present invention is described with specificity herein to meet statutory requirements. However, the description itself is not intended to necessarily limit the scope of claims. Rather, the claimed subject matter might be embodied in other ways to include different steps or combinations of steps similar to the ones described in this document, in conjunction with other present or future technologies. Although the terms “step” and/or “block” or “module” etc. might be used herein to connote different components of methods or systems employed, the terms should not be interpreted as implying any particular order among or between various steps herein disclosed unless and except when the order of individual steps is explicitly described. 
         [0019]    Furthermore, the described features, structures, or characteristics may be combined in any suitable manner in one or more embodiments. One skilled in the relevant art will recognize that the method may be practiced without one or more of the specific details, or with other methods, components, materials, and so forth. In other instances, well-known structures, materials, or operations are not shown or described in detail to avoid obscuring aspects of the invention. 
         [0020]    The schematic flow chart diagrams included herein are generally set forth as logical flow chart diagrams. As such, the depicted order and labeled steps are indicative of one embodiment. Other steps and methods may be conceived that are equivalent in function, logic, or effect to one or more steps, or portions thereof, of the illustrated method. Additionally, the format and symbols employed are provided to explain the logical steps of the method and are understood not to limit the scope of the method. Although various arrow types and line types may be employed in the flow chart diagrams, they are understood not to limit the scope of the corresponding method. Indeed, some arrows or other connectors may be used to indicate only the logical flow of the method&#39;s process. For instance, an arrow may indicate a waiting or monitoring period of unspecified duration between enumerated steps of the depicted process. Additionally, the order in which a particular method occurs may or may not strictly adhere to the order of the corresponding steps shown. 
         [0021]      FIG. 1  depicts, generally, a flowchart of one embodiment of the disclosed method, describing the process of mapping obstacles within a machine&#39;s workspace. This method produces a near-realtime workspace map by first taking pictures of the workplace. In the preferred embodiment, a camera has been mounted onto a crane trolley that automatically takes a picture at predefined points in the workspace while carrying on its normal operation. In each image, the background is detected, and the crane hook is masked. Once the obstacles are identified, a graphical representation of the workspace is generated. In order to eliminate noise in the images, the workspace images are first blurred. Blurring smooths the images by reducing image noise and details. Gaussian blur and median blur are two of the most commonly used methods for blurring and either or both may be used in this work. It is understood that other blurring techniques may be used in various embodiments of the present disclosure. Moreover, the means for reducing noise may not incorporate blurring or may only partially blur objects. In some embodied applications, median blur may be more desirable because it retains sharp edges while blurring. 
         [0022]    To separate the obstacles from the background, it is necessary to detect the background. If the background is known, a simple thresholding can be used to separate the background from the foreground. However, depending on the noise level and lighting, the background of the workspace may vary significantly. Moreover, the reflections of the lighting source and the shadows of the objects can make it difficult to distinguish the obstacles from the background using simple thresholding. A simple way to select the average background is calculating the image histogram for all the channels of a color image. It is assumed in this illustrative example that the background occupies a larger area than the obstacles. In this case, the most frequent pixel value is the selected background value for each channel. 
         [0023]    In some applications, the camera cannot capture the entire workspace in a single image. In such an application, numerous individual images will need to be taken and stitched together.  FIG. 2  shows an embodiment of the image acquisition process which is automated. In other embodiments, the image acquisition process may be performed manually. The workspace is divided into segment(s), and a picture is taken in each segment to cover the entire workspace. When the crane trolley reaches one of these regions, the camera automatically takes a picture. Then, it waits until it moves to another position or for a certain period of time if it stays at the same position, before taking the next picture. This automatic image acquisition works parallel to the normal crane operation. There is no stoppage time. However, for the first-time operation, it may be recommended that the crane be moved through the entire workspace. 
         [0024]    However, when this method is used for a crane, because the camera would be mounted directly over the crane hook, there will always be the crane hook/payload in the image. A simple solution is to cover that part of image with the background color calculated. One way to locate the hook in the image is using known methods for template matching. After locating the hook and calculating its dimensions, it can be masked. After masking, the images can be stitched together. 
         [0025]    Multiple known means can be used to stitch the images together. By way of illustrative example, the well-known OpenCV stitching pipeline can be used to stitch images, which uses automatic panoramic image stitching using invariant features. This algorithm can seamlessly stitch multiple images irrespective of order or brightness, which makes it suitable for the mapping algorithm. It can also handle small rotations and blends the images seamlessly. In this algorithm, the SIFT (scale-invariant feature transform) features of all the images to be stitched are extracted and matched. RANSAC (random sample consensus) is used to find the feature matches between images that are geometrically consistent, and a probabilistic model is used to verify those matches. Then, connected components of the images are found and bundle adjustment is performed to simultaneously solve for all the camera parameters. The images are then straightened and blended together using multi-band blending so that the output stitched image is smooth. 
         [0026]    Various techniques can be employed for foreground-background segmentation, including watershed transformation, graph partitioning methods, and region-growing methods, and integration of multiple cues. For illustrative purposes, a watershed transformation method is used in the instant embodiment because it generally provides closed contours with a low level of noise and low computation time. Thus, the watershed algorithm will be applied for obstacle detection. To do so, a marker image should be created where a portion of the foreground and background are marked. The foreground and the background of the image are segmented by the watershed algorithm based on these marked areas. To create the marker, the image is thresholded twice, through two three-channel scalars about the previously-selected background value. For the first thresholding operation, the threshold scalar range is larger, so that only the portions of image that fall outside the threshold range are sure to be the foreground and are marked as such. For the second thresholding operation, the threshold range is smaller, so that only the parts of the image that fall inside the threshold range are sure to be the background and are marked as background. Then, a marker is created and the aforementioned regions are labeled inside it. An example of such a marker image is shown in  FIG. 3 , where the background is gray, the foreground is white, and the rest of the image is black. 
         [0027]    Once the marker is determined, the watershed algorithm is applied to obtain the segmented image. The contours of the obstacles are extracted from the segmented image. Then, a polygonal curve is estimated and the contours are drawn, as can be seen in  FIG. 4 . Numerous means can be employed to estimate the polygonal curve including, but not limited to, an application of the Douglas-Peucker algorithm. 
         [0028]    The mapping process provided in this disclosure has the capability of taking both the latest and older positions of the obstacles into account. The older positions of obstacles can be used as an indicator of the likelihood of there being an obstacle at that location in the future. Each time a new picture is taken by the camera at a particular position, an individual map is generated by stitching that picture with the most recent pictures at other positions. Then, a final map is created by overlapping the latest map with older individual maps. The individual maps are overlapped in a way that the latest map is shown in red to indicate certainty of finding an obstacle. Older maps are shown in a different hue or color, such as yellow, than the new map(s), the intensity of which decreases with time when those maps were generated. For example, in one embodiment, the intensity can be set to decrease according to: 
         [0000]        I   i =100 e   −cm     2     t     1     /     (     t     0     −t     1)      
         [0000]    where I i  represents percentage intensity of i th  map, m is the number of maps available, c is a scaling factor, t i  represents time since i th  map, and t 1  and t 0  represent time since the most recent map and the oldest map, respectively. The scaling factor actually used can depend on the workspace conditions and the frequency with which the map is updated. For example, if the map is updated very often, a higher value of c may be chosen so that there is tangible contrast between maps. On the other hand, if the map is updated less often, a lower value of c may be chosen so that the older maps are still visible. 
         [0029]    Relatively recent maps are more likely to indicate an actual obstacle position. Therefore, to account for this shift through time, the intensity of older images decreases as time progresses to indicate the decreased certainty of finding an obstacle at that location. As shown in  FIG. 6 , the intensity depends both on number of images available and time when the image was taken. With respect to time, intensity approaches linearity when the number of images available is reduced, making sure that the images do not lose weight to quickly when not many images are available in a particular location. If there is an overlap in the obstacle locations from past images, the overlapped area is brighter than in the individual maps. The overlapped area indicates there has been an obstacle present at these locations in the workspace at multiple times in the past. Thus, the intensity can be used to suggest that the probability of finding an obstacle there in the future is greater such that a higher intensity corresponds with a higher probability of an obstacle being present. 
         [0030]    If an individual map is too old, it can be discarded as it is unlikely to indicate a probable future location of an obstacle. Moreover, if too many old maps are overlapped, the mapping may become cluttered and confusing to understand. To account for this issue, a memory factor can be used to determine the age and relativity of an individual map. The larger the memory factor is, the older an individual map can be and still be taken into account for generating the final map. For example, in an embodiment wherein the number of images is set to 2, the memory factor is calculated using: 
         [0000]        M   x,y   =t   0x,y   e   −nc1  if  n&gt; 2 
         [0000]      and 
         [0000]        M   x,y   =t   0x,y  if  n≦ 2 
         [0000]    where M x,y  is the memory factor at position (x, y), t 0x,y  is the time since the oldest image available at position (x, y), n represents number of images available at position (x, y), and c1 is a scaling factor. If an image at position (x, y) is older than M x,y,  then it is forgotten. At a particular location, the memory factor is a function of both number of images, n, and time since the oldest available image, t 0x,y . For a particular t 0x,y,  the memory factor reduces exponentially with number of images available. If a large number of images are available, the memory factor is smaller, so that more images are forgotten. If the number of images available is small, the memory factor becomes bigger, so that the older images are not forgotten. A maximum memory factor could be set up to make sure that the maximum number of images considered is limited, thereby reducing the chance of clutter by limiting the map to more relevant information. If the number of images available is less than or equal to two, no image is forgotten. As an example, individual maps at times T N , T N   _   1 , T N   _   2 , where N is number of images, are shown in  FIG. 5 . The resulting map is shown in  FIG. 6 , wherein the most recent positions, the next to most recent positions, and the oldest positions of the obstacles are shown in different hues or in varying intensity along with the overlapping areas of these positions. 
         [0031]    The application of the Method For Near-Realtime Workspace Mapping as described until this point depends, at least in part, on color-based image segmentation. Therefore, its application may be limited if there is not a good contrast between the background and the obstacles or if the background is of a substantially uneven color. To account for the issues with these situations, a second obstacle detection technique may also be employed concurrently with the application as described until this point which uses tags such as Quick Response (QR) codes to identify known obstacles in the workspace. These techniques can be used concurrently to produce a complete map of the workspace. Moreover, even in applications which do not have the color-based issues, the present system may still be set up to use tags like QR codes to readily account for the dimensions of known obstacles including commonly reoccurring obstacles or permanent obstacles. 
         [0032]    As previously discussed, because the performance of image-segmentation-based object detection technique can depend on the uniformity of the background and the contrast between the objects and the background, a QR code-based object detection technique may be combined with it to make it more robust. 
         [0033]    In general,  FIG. 7  shows the key steps of QR code-based portion of the mapping algorithm. In short, the most recent stitched image of the workspace is taken as the input to the mapping algorithm. All the QR codes in the stitched image are decoded, and the data are recorded. For each QR code found in the image, the database is searched for the matching object. When a match is found, the dimensions of the object and its relative position from the QR code are read from the database. The object position and orientation is calculated from the QR code position and orientation. Then, the top face of the object is drawn on the map. The process continues until all the objects labeled with QR codes read from the stitched image are drawn. Note, only obstacles labeled with QR codes are shown in this map. Therefore, this map will be combined with the image-segmentation-based map to obtain a more thoroughly complete map of the workspace. 
         [0034]    More specifically, since the mapping technique using QR codes works only for known objects, a database containing object types and dimensions is necessary for the algorithm. The position of each QR code relative to the object onto which it is affixed is also listed in the database. Every object in the database file is assigned with a code, which is also encoded in the QR code of the corresponding object. 
         [0035]    An example data entry for rectangular objects is shown in Table 1. Here, machine1 is a rectangular object, and r1 is the keyword for machine1. The QR code center is placed at a distance of (r x , r y ) units from the origin, which in this case is the lower left vertex of the rectangle relative to the QR code, as shown in  FIG. 8 . 
         [0000]    
       
         
               
             
               
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Data Entry System for Rectangular object R1 
               
             
          
           
               
                 machine1 
                 r x   
                 r y   
                 length 
                 width 
                 height 
                 rectangle 
               
               
                   
               
               
                 r1 
                 10 
                 9 
                 21 
                 17.25 
                 15 
                   
               
               
                   
               
             
          
         
       
     
         [0036]    To generate the map from the QR code data, the database is searched with the keywords from the decoded QR codes. It is generally preferable, although not necessary, that every keyword corresponds to a unique object. When a match is found, the dimensions of the object and the position of the QR code relative to the object is read from the database. Then, the center position and angle of the QR code are calculated. The object position and orientation are calculated from the QR code position and orientation. 
         [0037]    To draw rectangular objects, all the vertices are calculated from the center position and orientation of the QR code, as shown in  FIG. 8 . If the center of the QR code is C(x, y) and it is at an angle of θ with the horizontal axis, then the vertices O, A, B and D can be calculated using simple geometry. 
         [0038]    After all the vertices are found for the rectangle, it can be drawn by connecting the vertices with straight lines. Objects of other shapes can be drawn in a similar manner. The colors or hues of the objects may be depicted differently from the ones used in the image-segmentation-based map, so that the objects can be discerned in the combination map discussed later. 
         [0039]    Since the map is directly drawn from the dimensions specified in the database and the position and orientation of the QR codes, the accuracy of the map depends on the precision of measurements of the dimensions of the objects and the accuracy of placement of the QR codes. Distortion of the images captured by the camera, and distortion of the stitched image could also have an effect on the mapping accuracy. 
         [0040]    It can also be difficult to know the height and relative size of the objects from a map. A small object may seem larger than a big one if it is higher than the big object, because the top face of the small object is closer to the camera. This problem can be solved by adding the depth information of the objects. The height can be written in plain text on each object. Another way that a sense of depth of the objects can be given is by drawing the base of the objects. The object bases in the map vary in size and color-intensity depending on their height. The base becomes smaller and less bright with increasing height. The contrast and relative size between the top and the base give a sense of height of the objects. 
         [0041]    Since all the obstacles are not labeled with QR codes, the QR code-based mapping algorithm gives only a partial map of the workspace. To obtain a complete map of the workspace, the QR-code-based mapping method is combined with the image-segmentation-based mapping algorithm. To combine these two maps the QR code-based map is drawn directly over the image-segmentation-based map. 
         [0042]    For the purpose of understanding the Method For Near-Realtime Workspace Mapping, references are made in the text to exemplary embodiments of a Method For Near-Realtime Workspace Mapping, only some of which are described herein. It should be understood that no limitations on the scope of the invention are intended by describing these exemplary embodiments. One of ordinary skill in the art will readily appreciate that alternate but functionally equivalent components, materials, designs, and equipment may be used. The inclusion of additional elements may be deemed readily apparent and obvious to one of ordinary skill in the art. Specific elements disclosed herein are not to be interpreted as limiting, but rather as a basis for the claims and as a representative basis for teaching one of ordinary skill in the art to employ the present invention. Further, the disclosed method could be implemented on other machine applications than cranes. 
         [0043]    Reference throughout this specification to features, advantages, or similar language does not imply that all of the features and advantages that may be realized should be or are in any single embodiment. Rather, language referring to the features and advantages is understood to mean that a specific feature, advantage, or characteristic described in connection with an embodiment is included in at least one embodiment. Thus, discussion of the features and advantages, and similar language, throughout this specification may, but do not necessarily, refer to the same embodiment. 
         [0044]    Furthermore, the described features, advantages, and characteristics may be combined in any suitable manner in one or more embodiments. One skilled in the relevant art will recognize that the method may be practiced without one or more of the specific features or advantages of a particular embodiment. In other instances, additional features and advantages may be recognized in certain embodiments that may not be present in all embodiments. 
         [0045]    Reference throughout this specification to “one embodiment,” “an embodiment,” or similar language means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment. Thus, appearances of the phrases “in one embodiment,” “in an embodiment,” and similar language throughout this specification may, but do not necessarily, all refer to the same embodiment. 
         [0046]    It should be understood that the drawings are not necessarily to scale; instead, emphasis has been placed upon illustrating the principles of the invention. In addition, in the embodiments depicted herein, like reference numerals in the various drawings refer to identical or near identical structural elements. 
         [0047]    Moreover, the terms “substantially” or “approximately” as used herein may be applied to modify any quantitative representation that could permissibly vary without resulting in a change to the basic function to which it is related.