Information processing apparatus, control method, and program

An information processing apparatus (2000) detects leaving of an object to be determined from an object queue (20) included in video data (12) generated by a camera (10). The information processing apparatus (2000) infers a global behavior of the object to be determined on the basis of a relationship between the object to be determined and another object (22) included in the object queue (20). The information processing apparatus (2000) determines whether or not the object to be determined has left the object queue (20) on the basis of the global behavior of the object to be determined.

TECHNICAL FIELD

The present invention relates to image processing.

BACKGROUND ART

In various scenes, a queue is formed by objects such as persons. For example, the queue is formed at an immigration checkpoint of an airport, a bank ATM, a checkout of a store, or a platform of public transportation.

A technology for performing analysis and control on such a queue has been developed. For example, Patent Document 1 discloses a queue management system that can track an object having left the queue or an object cutting in the queue using a camera which is installed to be capable of capturing a monitoring region from immediately above. This system determines whether each object is in the queue or outside the queue using a queue behavior pattern parameter, such as a distance between the queue and the object, that represents a motion of the object. The leaving or cutting-in of the object is also determined using the queue behavior pattern parameter.

RELATED DOCUMENT

Patent Document

SUMMARY OF THE INVENTION

Technical Problem

In Patent Document 1, only a case where the object leaves in a direction orthogonal to a direction in which the queue is formed is considered with respect to the leaving of the object. However, the direction in which the object leaves is not limited to the direction orthogonal to the direction in which the queue is formed. For example, in a queue that is formed on a narrow aisle like a waiting queue formed at a checkout of a convenience store, the object leaves in a direction parallel to the direction in which the queue is formed. Leaving in such a case is not considered in the system of Patent Document 1.

In addition, in Patent Document 1, it is determined that cutting-in occurs in a case where the object is at a certain distance from the queue. In an actual scene of usage, there is also an object that simply passes near the queue, or an object that stays near the queue. In Patent Document 1, these objects are handled as “having a possibility of lining up in the queue”, and no further description is provided.

The present invention is conceived in view of the above problem. One object of the present invention is to provide a technology for detecting leaving of an object from an object queue or cutting-in with high accuracy.

Solution to Problem

An information processing apparatus of the present invention includes 1) a behavior inference unit that detects a first object and a second object included in an object queue using a captured image in which the object queue is included, and infers a global behavior of the first object based on a relationship between the first object and the second object, and 2) a determination unit that determines whether or not the first object has left the object queue on the basis of the inferred global behavior of the first object.

A control method of the present invention is executed by a computer. The control method includes 1) a behavior inference step of detecting a first object and a second object included in an object queue using a captured image in which the object queue is included, and inferring a global behavior of the first object based on a relationship between the first object and the second object, and 2) a determination step of determining whether or not the first object has left the object queue on the basis of the inferred global behavior of the first object.

A program of the present invention causes a computer to execute each step of the control method of the present invention.

Advantageous Effects of Invention

According to the present invention, a technology for detecting leaving of an object from an object queue or cutting-in with high accuracy is provided.

DESCRIPTION OF EMBODIMENTS

Hereinafter, example embodiments of the present invention will be described using the drawings. It should be note that in all of the drawings, the same constituents will be designated by the same reference signs, and descriptions of such constituents will not be repeated. In addition, in each block diagram, unless otherwise particularly described, each block does not represent a hardware unit configuration and represents a function unit configuration.

Summary

FIG. 1is a diagram for describing an operation of an information processing apparatus (information processing apparatus2000inFIG. 3described below) of Example Embodiment 1. The operation of the information processing apparatus2000in the following description is an illustration for easy understanding of the information processing apparatus2000. The operation of the information processing apparatus2000is not limited to the following example. Details and variations of the operation of the information processing apparatus2000will be described below.

The information processing apparatus2000detects leaving of an object22from an object queue20(the object queue20captured by a camera10) that is included in video data12generated by the camera10. The object queue20is a queue configured with objects22. InFIG. 1, the object queue20is configured with an object22-1to an object22-4among the object22-1to an object22-8included in a video frame14. The video frame14is one of time-series captured images constituting the video data12.

Any queue can be handled as the object queue20. For example, the object queue20is a queue of persons formed at an immigration checkpoint of an airport, a bank ATM, a checkout of a store, or a platform of public transportation. In this case, the objects22are persons. Besides, for example, the object queue20is a queue of vehicles waiting for using a parking lot. In this case, the objects22are vehicles. InFIG. 1, the objects22are persons.

A meaning of a term “leaving” in the present specification will be described. The object22included in the object queue20then may not be included in the object queue20anymore. This change is broadly divided into (1) a change in which the object22lines up in the object queue20and then, exits from the top and (2) a change in which the object22exits the object queue20in the middle of lining up in the object queue20.

Differences between (1) and (2) will be described using a queue of persons formed ahead of a checkout of a store as an example. A case of (1) is a case where a “person lining up in the queue proceeds and reaches the top of the queue and then, exits the queue from the top of the queue because the checkout is vacant, and purchases a product at the checkout”. On the other hand, a case of (2) is a case where a “person lining up in the queue exits the queue from the middle of the queue and does not purchase a product”.

In the present specification, “(2) the change in which the object22exits the object queue in the middle of lining up in the object queue20” will be referred to as “leaving”. This can also be referred to as “mid-leaving”. It should be noted that (1) can be referred to as “top-leaving” in contrast to the mid-leaving. Hereinafter, a case where “leaving” is simply used or a case where “mid-leaving” is used represents (2). On the other hand, a case where “top-leaving” represents (1).

The information processing apparatus2000determines whether or not the object22included in the object queue20has left the object queue20(hereinafter, referred to as a “leaving determination”). The object22that is an object on which the determination is to be performed by the information processing apparatus2000will be referred to as an object to be determined. For example, the information processing apparatus2000detects leaving of one or more objects22from the object queue20by sequentially performing the leaving determination on each object22included in the object queue20as the object to be determined.

In order to perform the leaving determination on the object to be determined, the information processing apparatus2000infers a behavior of the object to be determined based on a relationship between the object to be determined and another object22included in the object queue20. The information processing apparatus2000determines whether or not the object to be determined has left the object queue20on the basis of the inferred behavior.

The behavior of the object to be determined based on the relationship between the object to be determined and the other object22included in the object queue20represents a global behavior (a motion or a state) of the object to be determined related to the object queue20. Hereinafter, the behavior of the object to be determined based on the relationship between the object to be determined and the other object22included in the object queue20will be also referred to as a “global behavior of the object to be determined”.

The global behavior of the object to be determined may vary even in a situation where a behavior (a behavior focused on only the object to be determined without considering the relationship between the object to be determined and the other object22) of the object to be determined seen as an individual is the same. The behavior of a certain object focused on the object as an individual without considering the relationship between the object to be determined and the other object22will be referred to as a “local behavior of the object”.

FIG. 2is a diagram illustrating the local behavior and the global behavior of the object to be determined. In each of the examples of the left-hand queue and the right-hand queue inFIG. 2, the object to be determined is proceeding. Thus, the local behavior “proceeding” of the object to be determined is common.

On the other hand, between these two examples, the global behavior of the object to be determined is different. In the example of the left queue inFIG. 2, not only the object to be determined but also the object ahead of the object to be determined is proceeding. Thus, when the behavior of the object to be determined is globally seen, it is said that there is a high likelihood of the object to be determined proceeding in accordance with a motion of the whole object queue20. Thus, the global behavior of the object to be determined can also be represented as an “action of proceeding in the object20”.

In the example of the right queue inFIG. 2, the object to be determined is proceeding. On the other hand, the object ahead of the object to be determined is at a standstill. In this case, in a case where the behavior of the object to be determined is globally seen, it is said that there is a high likelihood that the behavior of the object to be determined is not proceeding in accordance with the motion of the whole object queue20and is proceeding so as to exit the object queue20(that is, leaving). Thus, the global behavior of the object to be determined can also be represented as an “action of leaving the object queue20”.

As in the latter case, when the global behavior of the object to be determined is focused, a situation where there is a high likelihood of leaving of the object to be determined may be recognized. Therefore, the information processing apparatus2000of the present example embodiment performs the leaving determination on the object to be determined by considering the global behavior of the object to be determined. Accordingly, leaving of the object to be determined can be detected earlier with high accuracy compared to that in a case where the global behavior of the object to be determined is not considered.

Hereinafter, the information processing apparatus2000of the present example embodiment will be described in further detail.

<Example of Functional Configuration of Information Processing Apparatus2000>

FIG. 3is a diagram illustrating a configuration of the information processing apparatus2000of Example Embodiment 1. For example, the information processing apparatus2000includes a behavior inference unit2020and a determination unit2040. Using the video frame14(captured image) in which the object queue20is included, the behavior inference unit2020infers the global behavior of the object to be determined on the basis of the relationship between the object to be determined included in the video frame14and the other object22in the object queue20. The determination unit2040performs the leaving determination on the object to be determined on the basis of the inferred global behavior of the object to be determined.

<Hardware Configuration of Information Processing Apparatus2000>

Each functional configuration unit of the information processing apparatus2000may be implemented by hardware (example: a hardwired electronic circuit) implementing each functional configuration unit, or may be implemented by a combination of hardware and software (example: a combination of an electronic circuit and a program controlling the electronic circuit). Hereinafter, a case where each functional configuration unit of the information processing apparatus2000is implemented by a combination of hardware and software will be described.

FIG. 4is a diagram illustrating a computer1000for implementing the information processing apparatus2000. The computer1000is any computer. For example, the computer1000is a personal computer (PC), a server machine, a tablet terminal, or a smartphone. Besides, for example, the computer1000may be the camera10. The computer1000may be a dedicated computer designed to implement the information processing apparatus2000or may be a general-purpose computer.

The computer1000includes a bus1020, a processor1040, a memory1060, a storage device1080, an input-output interface1100, and a network interface1120. The bus1020is a data transfer path for transmission and reception of data among the processor1040, the memory1060, the storage device1080, the input-output interface1100, and the network interface1120. A method of connecting the processor1040and the like to each other is not limited to bus connection. The processor1040corresponds to various processors such as a central processing unit (CPU) and a graphics processing unit (GPU). The memory1060is a main storage device that is configured with a random access memory (RAM) or the like. The storage device1080is an auxiliary storage device that is configured with a hard disk, a solid state drive (SSD), a memory card, a read only memory (ROM), or the like.

The input-output interface1100is an interface for connecting the computer1000to input-output devices. The network interface1120is an interface for connecting the computer1000to a communication network. For example, the communication network is a local area network (LAN) or a wide area network (WAN). A method of connecting the network interface1120to the communication network may be wireless connection or may be wired connection.

For example, the computer1000is communicably connected to the camera10through the network. A method of communicably connecting the computer1000to the camera10is not limited to connection through the network. In addition, the computer1000may not be communicably connected to the camera10.

The storage device1080stores a program module that implements each functional configuration unit (the behavior inference unit2020and the determination unit2040) of the information processing apparatus2000. The processor1040implements a function corresponding to each program module by reading each program module into the memory1060and executing the program module.

It should be noted that the computer1000may be implemented using a plurality of computers. For example, the behavior inference unit2020and the determination unit2040can be implemented by different computers. In this case, the program module stored in the storage device of each computer may be only a program module corresponding to the functional configuration unit implemented by the computer.

The camera10is any camera that generates the video data12by generating the time-series video frame14by repeatedly performing capturing. For example, the camera10is a surveillance camera that is disposed for surveillance of a determined facility, road, and the like.

As described above, the computer1000implementing the information processing apparatus2000may be the camera10. In this case, the camera10performs the leaving determination on the object to be determined by analyzing the video frame14generated by the camera10. As the camera10having such a function, for example, a camera called an intelligent camera, a network camera, or an Internet Protocol (IP) camera can be used.

It should be noted that not all functions of the information processing apparatus2000may be implemented by the camera10, and only a part of the functions of the information processing apparatus2000may be implemented by the camera10. For example, a function of detecting the object22from the video frame14is implemented by the camera10, and a function of performing the leaving determination on the object to be determined by analyzing the action and the like of each detected object22is implemented by a server apparatus. In this case, the server apparatus acquires various information (detection information described later) such as the position and an image feature of the detected object22from the camera10. In this case, the server apparatus may not acquire the video frame14.

<Method of Acquiring Video Frame14>

The information processing apparatus2000acquires one or more video frames14to be processed. Various methods of acquiring the video frame14by the information processing apparatus2000are present. For example, the information processing apparatus2000receives the video frame14transmitted from the camera10. Alternatively, for example, the information processing apparatus2000accesses the camera10and acquires the video frame14stored in the camera10.

It should be noted that the camera10may store the video frame14in a storage device that is disposed outside the camera10. In this case, the information processing apparatus2000acquires the video frame14by accessing the storage device. Thus, in this case, the information processing apparatus2000and the camera10may not be communicably connected.

In a case where a part or all of the functions of the information processing apparatus2000are implemented by the camera10, the information processing apparatus2000acquires the video frame14generated by the information processing apparatus2000. In this case, for example, the video frame14is stored in a storage device (for example, the storage device1080) inside the information processing apparatus2000. Therefore, the information processing apparatus2000acquires the video frame14from the storage device.

A timing at which the information processing apparatus2000acquires the video frame14is not limited. For example, each time a new video frame14constituting the video data12is generated by the camera10, the information processing apparatus2000acquires the newly generated video frame14. Besides, for example, the information processing apparatus2000may periodically acquire a video frame14that is not acquired. For example, in a case where the information processing apparatus2000acquires the video frame14once in one second, the information processing apparatus2000collectively acquires a plurality of video frames14(for example, 30 video frames14in a case where a frame rate of the video data12is 30 frames/second (fps)) that are generated in one second by the camera10.

The information processing apparatus2000may acquire all video frames14constituting the video data12or may acquire only a part of the video frames14. In the latter case, for example, the information processing apparatus2000acquires the video frames14generated by the camera10at a ratio of one to a predetermined number.

<Detection and Management of Object Queue20>

As a premise for performing the leaving determination on the object to be determined, the information processing apparatus2000detects and manages the object queue20. For example, the management of the object queue20is implemented by generating and updating tracking information for the object22included in the object queue20. Hereinafter, the object22included in the object queue20will be referred to as an object to be tracked.

The tracking information shows various information related to the object to be tracked. For example, the tracking information shows a position, a size, a distance to the object queue20, and identification information for each object to be tracked. The identification information is an identifier or the like that is assigned to each object to be tracked in order to discriminate objects to be tracked from each other. Furthermore, the tracking information shows local information that represents a local behavior of the object to be tracked, and global information that represents a global behavior of the object to be tracked.

The position of the object to be tracked may be represented as a position on the video frame14(for example, coordinates using the upper left end of the video frame14as an origin) or may be represented as real world coordinates. Existing technologies can be used as a technology for computing the real world coordinates of an object included in an image generated by a camera. For example, the real world coordinates of the object to be tracked can be computed from the position on the video frame14using parameters representing a position and a posture acquired by calibrating the camera. Similarly, the distance between the object to be tracked and the object queue20may be a distance in the video frame14or a distance in the real space. It should be noted that a specific method of determining the distance between the object to be tracked and the object queue20will be described later.

Information shown in the tracking information is not limited to the above information. For example, the tracking information may further show a position from the top of the object queue20, an elapsed time from registration in the tracking information, an inferred waiting time, an image feature, and an image region for each object22. The inferred waiting time of the object22means a time required until the top-leaving of the object22from the current time point.

For example, a feature value describing a size, a shape, or a color or a pattern (in a case of a person, a color or a pattern of clothes) of a surface of the object to be tracked can be used as the image feature of the object to be tracked. More specifically, a feature value such as a color histogram, a color layout, an edge histogram, or a Gabor feature can be used. In addition, for example, a shape descriptor standardized in MPEG-7 can be used as the feature value representing the shape of the object to be tracked.

The image region of the object to be tracked is information that defines the image region representing the object to be tracked. For example, in a case where a rectangle that is circumscribed about the object to be tracked is used as the image region representing the object to be tracked, the image region is information (for example, coordinates of the upper left end and the lower right end) defining the rectangle.

FIG. 5is a diagram illustrating the tracking information in a table format. The table inFIG. 5will be referred to as a table200. The table200shows a tracking ID202, a position204, a distance206, local information208, global information210, and an image feature212. The tracking ID202shows an identifier assigned to the object to be tracked. The distance206shows the distance between the object to be tracked and the object queue20.

The tracking information is stored in a storage region. For example, the storage region is the storage device1080inFIG. 3. The storage region in which the tracking information is stored is not limited to the storage region disposed inside the information processing apparatus2000. For example, the tracking information may be stored in a storage region such as the server apparatus or a network attached storage (NAS) outside the information processing apparatus2000. In this case, the information processing apparatus2000transmits the generated tracking information to the server apparatus or the like.

Hereinafter, generation and update of the tracking information will be described. The generation of the tracking information means that when the object queue20is detected from the video frame14, new tracking information is generated for the object queue20. Using the video frame14in which the object queue20is detected, the information processing apparatus2000generates the tracking information using each object22included in the object queue20in the video frame14as the object to be tracked.

The update of the tracking information means that the object22is detected from the video frame14that is generated after the detection of the object queue20, and a content of the tracking information is changed on the basis of information related to the detected object22. For example, a change in position and the like of the object to be tracked is reflected on the tracking information. In addition, information related to the object22newly added to the object queue20is added to the tracking information. Furthermore, information related to the object22that has left the object queue20is deleted from the tracking information. The information related to the object22having left the object queue20may remain in the tracking information. In this case, the tracking information is configured such that the object22belonging to the object queue20can be differentiated from the object22having left the object queue20(for example, a flag is provided).

FIG. 6is a flowchart illustrating a summary of a flow of process executed by the information processing apparatus2000. The information processing apparatus2000detects the object queue20from the video frame14(S102). The information processing apparatus2000generates the tracking information using the objects22included in the detected object queue20as the objects to be tracked (S104).

S106to S110correspond to a loop process A that is repeatedly executed until a predetermined end condition is satisfied. In S106, in a case where the predetermined end condition is satisfied, the information processing apparatus2000ends the process inFIG. 6. On the other hand, in a case where the predetermined end condition is not satisfied, the process inFIG. 6proceeds to S108.

In S108, the information processing apparatus2000updates the tracking information. S110is the end of the loop process. Thus, the process inFIG. 6proceeds to S106. By repeatedly executing the loop process A until the predetermined end condition is satisfied, the tracking information is repeatedly updated. In addition, each time the tracking information is updated, the leaving determination is performed for each object to be tracked.

The predetermined end condition is not limited. For example, the predetermined end h condition is that the number of objects22included in the object queue20is 0, that is, the object queue20is not present. In this case, the information processing apparatus2000executes the process inFIG. 6again from the beginning for the video data12configured with the video frame14that is not set to be processed yet. By doing so, detection of the newly formed object queue and detection of a change of the object queue20are performed.

<<Detection of Object Queue20>>

The information processing apparatus2000detects the object queue20from the video data12by sequentially performing image analysis on a plurality of time-series video frames14constituting the video data12. The video frame14used in the detection of the object queue20may be a part of the video frames14constituting the video data12. For example, the information processing apparatus2000performs the image analysis on the time-series video frames14constituting the video data12at a ratio of one to a predetermined number.

In order to detect the object queue20, the information processing apparatus2000detects the object22from the video frame14. Various known technologies can be used as a technology for detecting the object22from the video frame14. For example, the information processing apparatus2000includes a detector that is caused to learn the image feature of the object to be detected from the video frame14. For example, in a case where a person is handled as the object22, the detector learns an image feature representing characteristics of a person. In addition, in a case where a vehicle is handled as the object22, the detector learns an image feature representing characteristics of a vehicle.

The detector detects an image region matching the learned image feature from the video frame14as a region (hereinafter, an object region) representing the object. The detection of the object region means that the object represented by the object region is detected. For example, a detector that performs detection based on a histograms of oriented gradients (HOG) feature or a detector that uses a convolutional neural network (CNN) can be used as the detector representing the object22. Note that the detector may be learned to detect the region of the whole object or may be learned to detect a part of the region of the object (for example, a head portion of a person).

The detector outputs information (hereinafter, detection information) related to the detected object22. For example, the detection information shows a position, a size, identification information, an image feature, and an image region of the detected object22. The identification information is an identifier or the like for discriminating the objects22detected from the video frame14from each other. In addition, after the object queue20is detected, the detector may compute a distance between the object22and the object queue20and include the distance in the detection information.

Various existing technologies can be used as a technology for detecting the formation of the object queue20by the object22included in the video frame14. A region (hereinafter, a queue area) in which the object queue20is formed may be determined as a part of the image region of the video frame14. In this case, depending on the detection of one or more objects22in the queue area, the information processing apparatus2000determines that the object queue20is formed by the one or more objects22.

A method of defining the queue area can be implemented using various known methods of specifying a region in the captured image generated by the camera. For example, the information processing apparatus2000receives an input operation of specifying the queue area from a user. For example, this input operation is an operation of drawing an area in which the object queue20is formed on the video frame14using any figure such as a line, a polygon, or a circle. Besides, for example, the specifying of the queue area may be implemented by specifying coordinates (for example, in a case where the queue area is a rectangle, the coordinates of the upper left end and the lower right end) for determining the queue area by a keyboard input.

The information processing apparatus2000may detect the object22using the whole image region of the video frame14as a target or may detect the object22using only a part of the image region as a target. For example, in a case where the queue area is defined, the information processing apparatus2000may detect the object22from only the queue area as a target or may detect the object22from only the queue area and its surrounding area (for example, an area obtained by enlarging the queue area at a predetermined magnification) as a target.

The shape of the object queue20may be linear or may not be linear. The latter case is a case where the object queue20is curved in an S shape or is folded in the middle of the object queue20.FIG. 7is a diagram illustrating the object queue20having a non-linear shape. In a case where the shape of the object queue20is not linear, for example, a queue line30is defined along the object queue20, and a state, a movement direction, and the like of the object queue20are defined along the queue line30. The queue line represents (is similar to) the shape of the object queue20by a line.

For example, the distance between the object22and the object queue20is defined using the queue line. Specifically, a length of a perpendicular line extending from the object22to the queue line of the object queue20is handled as the distance between the object22and the object queue20.

<<Flow of Process of Updating Tracking Information>>

FIG. 8is a flowchart illustrating a flow of process of updating the tracking information.FIG. 8is a detailed process executed in S108inFIG. 6.

The information processing apparatus2000performs the process illustrated inFIG. 8using each video frame14after the video frame14in which the object queue20is detected as a target.

The information processing apparatus2000detects the object22from the video frame14(S202). The information processing apparatus2000associates the object22detected from the video frame14with the object to be tracked (S204). Existing technologies can be used as a technology for associating the object detected from the video frame14with the object to be tracked (the object detected from a previous video frame14) shown in the tracking information.

The information processing apparatus2000infers the local behavior of each object to be tracked (S206). The information processing apparatus2000infers the global behavior of each tracking target (S208). The information processing apparatus2000performs the leaving determination for each object to be tracked (S210).

The information processing apparatus2000updates the content of the tracking information (S212). Existing technologies can be used as a technology for updating the content of the tracking information. For example, the information processing apparatus2000deletes the object to be tracked (the object to be tracked performing the top-leaving or the mid-leaving) that is not included in the object queue20anymore from the tracking information. As described above, the information related to the object to be tracked that is not included in the object queue20anymore may remain in the tracking information. In addition, the information processing apparatus2000adds the object22(the object22that is newly added to the object queue20from the tail of the object queue20, or the object22that cuts in the object queue20) that is newly included in the object queue20to the tracking information as a new object to be tracked. Furthermore, the information processing apparatus2000changes the information (the position and the like) of the object to be tracked that is shown in the tracking information and is continuously included in the object queue20using the detection information of the object22associated with the object to be tracked.

The information processing apparatus2000infers the local behavior for each object to be tracked. For example, the local behavior of the object to be tracked is defined as a state (hereinafter, a motion state) related to a motion of the object to be tracked. For example, the motion state of the object to be tracked is any one of a proceeding state, a receding state, and a standstill state.

For example, the local behavior of the object to be tracked detected from a certain video frame14can be inferred from a change in position of the object to be tracked in a predetermined period in the past including a generation time point of the video frame14. For example, the information processing apparatus2000computes a vector connecting the position of the object to be tracked detected from a video frame14-1to the position of the object to be tracked detected from an immediately previously generated video frame14-2as a movement vector of the object to be tracked in the video frame14-1. The local behavior of the object to be tracked in the video frame14-1is inferred on the basis of a direction of the movement vector and a magnitude (motion amount) of the movement vector.

For example, the information processing apparatus2000determines whether or not the object to be tracked is at a standstill on the basis of the magnitude of the movement vector of the object to be tracked. Specifically, in a case where the magnitude of the movement vector is less than or equal to a reference value, the information processing apparatus2000determines that the object to be tracked is at a standstill. The reference value may be zero or a value greater than zero. In the former case, the local behavior of the object to be tracked is handled as the standstill state only in a case where the object to be tracked is not moving. On the other hand, in the latter case, even in a case where the object to be tracked is moving, the local behavior of the object to be tracked is handled as the standstill state in a case where the motion amount is less than or equal to the reference value. It should be noted that the reference value may be fixedly set in advance in the information processing apparatus2000or may be specified by the user of the information processing apparatus2000.

The reference value may be a statically decided value or a dynamically decided value. In the former case, the reference value is stored in advance in a storage device that can be accessed from the information processing apparatus2000. In the latter case, the information processing apparatus2000dynamically computes the reference value. For example, the information processing apparatus2000computes a moving average of the motion amount in the past in a time direction and uses a computed value as the reference value.

For the object to be tracked that is not at a standstill, a determination as to whether or not the object to be tracked is in the proceeding state or the receding state is performed on the basis of the direction of the movement vector. For example, the information processing apparatus2000computes a component of the movement vector of the object to be tracked that is parallel to a proceeding direction of the object queue20. In a case where the component is the same as the proceeding direction of the object queue20, the information processing apparatus2000sets the local behavior of the object to be tracked to the “proceeding state”. On the other hand, in a case where the component is in a direction opposite to the proceeding direction of the object queue20, the information processing apparatus2000sets the local behavior of the object to be tracked to the “receding state”.

The behavior inference unit2020infers the global behavior for each object to be tracked. The behavior inference unit2020infers the global behavior of the object to be tracked on the basis of the local behavior of the object to be tracked and the local behavior of another object to be tracked. The global behavior of the object to be tracked represents a meaning of the local behavior of the object to be tracked on the basis of a relationship between the object to be tracked and the other object to be tracked.

For example, the information processing apparatus2000infers the global behavior of the object to be tracked on the basis of a combination of the local behavior of the object to be tracked and the local behavior of the other object to be tracked (for example, the object to be tracked positioned immediately ahead or behind) adjacent to the object to be tracked.FIG. 9is a first diagram illustrating a table showing the global behavior of the object to be tracked.FIG. 9illustrates a global behavior of an object to be tracked A in association with a combination of a local behavior of the object to be tracked A and a local behavior of an object to be tracked B. The object to be tracked B is the object to be tracked that is positioned immediately ahead of the object to be tracked A.

For example, a row in which the local behavior of the object to be tracked A shows the “proceeding state” is focused. In this case, in a case where the local behavior of the object to be tracked B is the “proceeding state”, the global behavior of the object to be tracked A is “proceeding in the queue”. Since both of the object to be tracked A and the object to be tracked B immediately ahead thereof are proceeding, the object to be tracked A can be inferred to be proceeding in accordance with the whole object queue20.

On the other hand, in a case where the local behavior of the object to be tracked B is the “standstill state”, the global behavior of the object to be tracked A is a “leaving action”. Since the object to be tracked A is proceeding regardless of the standstill of the object to be tracked B immediately ahead, the object to be tracked A can be inferred to be proceeding in order to leave the object queue20.

In addition, in a case where the object to be tracked A is at a standstill and the object to be tracked B is proceeding, it is said that the object to be tracked A is in a state where the object to be tracked A is at a standstill but can proceed in the object queue20. Thus, the global behavior of the object to be tracked A is “being able to proceed in the queue”.

As a target for comparison with the object to be determined, instead of one object to be tracked lining up immediately ahead thereof, a predetermined number (two or more) of objects to be tracked lining up ahead of the object to be determined may be used. In this case, for example, the behavior inference unit2020handles the predetermined number of objects to be tracked as one group and infers a local behavior of the group. The group simply means a collection of a plurality of objects to be tracked and does not require an attribute or the like common to the objects to be tracked.

For example, the global behavior of the object to be determined that is determined by the local behavior of the object to be determined and the local behavior of the group of objects to be tracked lining up ahead thereof can be represented by replacing the “object to be tracked B” with the “group of objects to be tracked lining up ahead of the object to be tracked A” inFIG. 9.

For example, the local behavior of the group is determined on the basis of the local behavior of each object to be tracked included in the group. For example, the behavior inference unit2020sets the local behavior of the group to “standstill” in a case where a predetermined ratio or more of objects to be tracked are at a standstill among the objects to be tracked included in the group. Similarly, the behavior inference unit2020sets the local behavior of the group to “proceeding” in a case where a predetermined ratio or more of objects to be tracked are proceeding, and sets the local behavior of the group to “receding” in a case where a predetermined ratio or more of objects to be tracked are receding.

The global behavior of the object to be determined may be determined by considering not only the other object to be tracked lining up immediately ahead of the object to be determined but also the other object to be tracked lining up immediately behind the object to be determined.FIG. 10is a second diagram illustrating a table showing the global behavior of the object to be tracked. The object to be tracked B is positioned immediately ahead of the object to be tracked A, and an object to be tracked C is positioned immediately behind the object to be tracked A.

FIG. 10illustrates the global behavior of the object to be tracked A in association with a combination of local behaviors of the objects to be tracked A, B, and C. For example, a row in which the object to be tracked B is in the “proceeding state” and the object to be tracked C is in the “proceeding state” is focused. In this case, in a case where the local behavior of the object to be tracked A is the “proceeding state”, the global behavior of the object to be tracked A is “proceeding in the queue”. This is the same as a case where the object to be tracked A is in the “proceeding state” and the object to be tracked B is in the “proceeding state” inFIG. 9.

By further reflecting the local behavior of the object to be tracked C lining up immediately behind the object to be tracked A, the global behavior of the object to be tracked A can be inferred with higher accuracy.

The determination unit2040performs the leaving determination for each object to be tracked. As described above, the object for which the leaving determination is to be performed is referred to as the object to be determined.

The determination unit2040computes a likelihood of the object to be determined having left the object queue20on the basis of the global behavior of the object to be determined. The computed likelihood will be referred to as a leaving likelihood. The determination unit2040determines whether or not the object to be determined has left the object queue20on the basis of the leaving likelihood. For example, in a case where the leaving likelihood computed for a certain object to be determined is greater than or equal to a predetermined value, the determination unit2040determines that the object to be determined has left the object queue20. On the other hand, in a case where the leaving likelihood computed for a certain object to be determined is less than the predetermined value, the determination unit2040determines that the object to be determined does not leave the object queue20.

Besides, for example, the determination unit2040may determine that the object to be determined has left the object queue20only in a case where a situation where the leaving likelihood of the object to be determined is greater than or equal to the predetermined value continues for a predetermined period. Besides, for example, the determination unit2040may compute a statistic value of the leaving likelihood of the object to be determined in the predetermined period and determine that the object to be determined has left the object queue20only in a case where the statistic value is greater than or equal to the predetermined value. For example, the statistic value is an average value, a cumulative value, a maximum value, or a minimum value.

The determination unit2040computes the leaving likelihood using various parameters related to the object to be determined. Here, a function of outputting the leaving likelihood on the basis of the input parameters will be referred to as a leaving likelihood function. Types of parameters used by the leaving likelihood function will be described later.

The global behavior of the object to be determined is reflected on the leaving likelihood obtained using the leaving likelihood function. For example, in a case where values of the parameters provided to the leaving likelihood function are fixed, the leaving likelihood obtained using the leaving likelihood function is set to vary depending on the global behavior of the object to be determined. More specifically, in a situation where the values of the parameters provided to the leaving likelihood function are the same, the leaving likelihood computed in a case where the global behavior of the object to be determined is the “leaving action” is set to be greater than the leaving likelihood computed in a case where the global behavior of the object to be determined is other than the “leaving action”. For example, two leaving likelihood functions f1and f2are prepared. f1and f2are designed so that f1outputs a greater value than f2in a case where parameters having the same values are input into f1and f2. The determination unit2040uses the leaving likelihood function f1in a case where the global behavior of the object to be determined is the “leaving action”, and uses the leaving likelihood function f2otherwise. For example, f1can be set as a function of multiplying an output value of f2by a predetermined value greater than 1.

Hereinafter, the leaving likelihood function will be further described with focus on the parameters used in the leaving likelihood function.

For example, the parameters used in the leaving likelihood function include a distance between the object to be determined and the object to be tracked that is adjacent to the object to be determined in a proceeding direction of the object to be determined. For example, the “object to be tracked adjacent to the object to be determined in the proceeding direction of the object to be determined” means the object to be tracked positioned immediately ahead of the object to be determined in a case where the object to be determined is proceeding, and means the object to be tracked positioned immediately behind the object to be determined in a case where the object to be determined is receding. For example, a function that does not monotonically decrease along with a decrease of the distance is used as the leaving likelihood function that uses the distance between the object to be determined and the adjacent object to be tracked as a parameter.

Besides, for example, the parameters used in the leaving likelihood function includes a distance between the object to be determined and the object queue20. For example, a function that does not monotonically decrease along with an increase of the distance is used as the leaving likelihood function that uses the distance between the object to be determined and the object queue20as a parameter.

FIG. 11is a schematic diagram of a case where the object queue20is seen from immediately above. It is assumed that the object22-2is the object to be determined. InFIG. 11, the object22-2is proceeding. Therefore, the determination unit2040inputs d1that is a distance between the object22-2and the object22-1positioned immediately ahead of the object22-2into the leaving likelihood function. Furthermore, the determination unit2040inputs a length d2(a distance between the object22-2and the object queue20) of a perpendicular line32that extends to the queue line30of the object queue20from the object22-2.

It should be noted that in the example inFIG. 11, a distance between the objects to be tracked is defined as a difference in position in a queue line direction. However, the distance between the objects to be tracked may be represented as a length or the like of a straight line connecting centers of the objects to be tracked.

Besides, for example, the parameters used in the leaving likelihood function may further include a difference between the position in queue (a value representing an ordinal number from the top) of the last object to be tracked of proceeding objects to be tracked and the position in queue of the object to be determined. Usually, in a case where the whole object queue20is at a standstill, and then the top proceeds, a proceeding motion sequentially propagates from the top such that the second object subsequently proceeds and the third object subsequently proceeds. Thus, for example, in a case where the top and the second object are proceeding and the third object is at a standstill, there is a possibility that proceeding of the fourth and later objects represents a sign of leaving of the objects.

Therefore, the leaving likelihood can be obtained with higher accuracy using the difference between the position in queue of the last object to be tracked (the second object in the above example) of the proceeding objects to be tracked and the position in queue of the object to be determined as a parameter of the leaving likelihood function. The leaving likelihood function is a function that does not monotonically decrease along with an increase of the difference between the position in queue of the last object to be tracked of the proceeding objects to be tracked and the position in queue of the object to be determined.

Besides, for example, an angle between a movement direction of the object to be determined and a movement direction of the object to be tracked adjacent in the movement direction of the object to be determined may be used as the parameters constituting the leaving likelihood function. Usually, it is considered that the objects lining up in the object queue20move in almost the same direction as the proceeding direction of the object queue20. However, it is considered that a large amount of component of a direction orthogonal to the proceeding direction of the object queue20is included in the movement direction of the leaving object. Accordingly, the angle between the movement direction of the object to be determined and the movement direction of the object to be tracked positioned in the leaving direction thereof can be used as a parameter. For example, in the leaving likelihood function, the angle is applied to any trigonometric function.

Besides, for example, the parameters used in the leaving likelihood function may use a difference in movement velocity between the object to be determined and the object to be tracked adjacent to the object to be determined in the proceeding direction of the object to be determined. A case where the object to be determined is leaving forward is considered. In this case, the object to be determined passes by the tracking target lining up immediately ahead of the object to be determined. Thus, a movement velocity of the object to be determined is higher than a movement velocity of the object lining up immediately ahead thereof. Accordingly, the difference between the movement velocity of the object to be determined and the movement velocity of the object to be tracked lining up immediately ahead thereof can be used as a parameter. For example, the leaving likelihood function is a function that does not monotonically decrease along with an increase of the difference in movement velocity.

Besides, for example, the leaving likelihood may be computed as follows. First, a predetermined region is determined as follows on the basis of a distance in which the object to be determined can approach the object to be tracked lining up immediately ahead.FIG. 12is a diagram illustrating the predetermined region. Reference sign24denotes the object to be determined. Reference sign50denotes the predetermined region.

The determination unit2040determines a reference point40from a history of a position of the object to be determined24. For example, the object to be determined24moving as inFIG. 12is assumed. In this case, first, a point of the queue line that has a shortest distance from the position of the object to be determined24at each time in a movement history of the object to be determined24in the past is obtained as a possible reference point40. Among the possible reference points, the most recent possible reference point in time-series is handled as the reference point40. In addition, the reference point40may be determined using the local behavior of the object to be determined24together. In this case, among the possible reference points40, the possible reference point that is most recent in time-series and at which the local behavior of the object to be determined24at a time point of the possible reference point is the “standstill state” is selected as the reference point40.

The region50is an ellipse determined by a first diameter (a short diameter inFIG. 12) of a length r1and a second diameter (a long diameter inFIG. 12) of a length r2. r1denotes a distance in which the object to be determined positioned at the reference point40can approach the object22lining up immediately ahead. For example, this distance is a length obtained by subtracting a predetermined margin from a distance between the reference point40and the object22.

r2denotes a predetermined distance that is determined in advance. In a case where the object to be tracked moves in a direction at a right angle with respect to the object queue20, a distance by which the object to be tracked may be handled as exiting the object queue20is denoted by r2.

The determination unit2040computes the distance d1between the reference point40and the current object to be determined24. Furthermore, the determination unit2040obtains a position at which a straight line extending to the current object to be determined24from the reference point40intersects with a boundary line of the region50. The determination unit2040obtains the distance d2between the computed position and the reference point40.

The determination unit2040uses a ratio (d1/d2) of d1to d2as a parameter to be input into the leaving likelihood function. For example, a function that does not monotonically decrease along with an increase of d1/d2can be used as the leaving likelihood function.

For example, as a method of considering the global behavior of the object to be determined24, a method of changing a size of the region50on the basis of the global behavior of the object to be determined24is present. As the size of the region50is decreased, it is more easily determined that the object to be determined24has left the object queue20. Therefore, for example, the size of the region50in a case where the global behavior of the object to be determined24is the “leaving action” is set to be less than the size of the region50in a case where the global behavior of the object to be determined24is other than the “leaving action”. The size of the region50can be changed by changing one or both of r1and r2.

It should be noted that in the above example, the reference point40is set using the object to be determined24as a reference. Alternatively, the reference point40may be the position of the object22that is positioned in a direction in which the object to be determined24moves. For example, in a case where the object to be determined24is proceeding, the position of the object22lining up immediately ahead of the object to be determined24is set as the reference point. In this case, the determined region can be interpreted as a region in which the object22present in the movement direction of the object to be determined24is not to be approached anymore.

FIG. 13is a block diagram illustrating a functional configuration of the information processing apparatus2000of Example Embodiment 2. The information processing apparatus2000of Example Embodiment 2 has the same function as the information processing apparatus2000of Example Embodiment 1 except for the points described below. The information processing apparatus2000of Example Embodiment 2 may perform the leaving determination on the object to be tracked using existing technologies.

The information processing apparatus2000of Example Embodiment 2 detects the object22from the video data12and detects the object queue20configured with the objects22in the same manner as the information processing apparatus2000of Example Embodiment 2. The tracking information is generated and updated in order to manage the objects22(objects to be tracked) included in the object queue20.

The information processing apparatus2000of Example Embodiment 2 detects the object22that cuts in the object queue20. A term “cutting-in” will be described. A change in which a new object22is added to the object queue20is broadly divided into (1) a change in which a new object22is added to the object queue20from the tail of the object queue20and (2) a change in which a new object22is added to the object queue20from a part other than the tail of the object queue20by cutting in between two objects22already lining up in the object queue20. In the present specification, a case of (2) will be referred to as “cutting-in”. A case of (1) will be referred to as “normal addition”.

More specifically, first, the information processing apparatus2000determines whether or not the object22detected from the video frame14is present close to the object queue20. Furthermore, the information processing apparatus2000associates each object22determined as being present closet to the object queue20with the object to be tracked included in the tracking information.

The object22for which the associated object to be tracked is not present regardless of the determination that the object22is present close to the object queue20may be present. As such an object22, for example, (1) the object22that tries to be normally added to the object queue20, (2) the object that tries to cut in the object queue20, (3) the object that is passing near the object queue20, or (4) the object that is staying near the object queue20is considered.

In a case where the object22is the object added to the object queue20, the object22is a normally added object in a case where the object22is positioned behind the object to be tracked positioned at the tail of the object queue20. On the other hand, in a case where the object22is positioned ahead of the object to be tracked positioned at the tail of the object queue20, the object22is an object that cuts in.

Therefore, the information processing apparatus2000of Example Embodiment 2 handles the object22positioned ahead of the object to be tracked positioned at the tail of the object queue20as a second object to be determined. The information processing apparatus2000determines whether or not the second object to be determined cuts in the object queue20(whether or not the second object to be determined is the object22corresponding to (2)). Hereinafter, this determination will be referred to as a cutting-in determination.

In a case where the cutting-in determination is performed, the information processing apparatus2000infers a global behavior of the second object to be determined based on a relationship between the second object to be determined and the other object22included in the object queue20. The information processing apparatus2000performs the cutting-in determination on the second object to be determined based on the inferred global behavior.

A change of the object22(object to be tracked) that occurs in the object queue20in a case where the second object to be determined cuts in the object queue20will be described. In a case where a new object22cuts in the object queue20, an interval between the objects to be tracked near a location at which cutting-in occurs is decreased from the interval before the occurrence of cutting-in.FIG. 14is a schematic diagram when the object queue20is seen from immediately above. A diagram at the left end illustrates a situation before cutting-in occurs. All of the object22-1to the object22-3are objects to be tracked. Each object22is lined up at an equal interval of 70 cm.

A diagram at the center illustrates a situation in which cutting-in occurs. The object22-4cuts in between the object22-1and the object22-2. In a case where the object22-4cuts in between the object22-1and the object22-2, the interval between the objects is decreased from 70 cm.

A diagram at the right end illustrates a situation after cutting-in occurs. In a case where cutting-in occurs, the interval between the objects is naturally adjusted by gradual receding of each object to be tracked behind the location at which cutting-in occurs. Finally, the interval between the objects22becomes approximately the same as the original interval (70 cm). In actuality, the interval is generally slightly narrower than the interval before cutting-in occurs.

In a case where the object22cuts in the object queue20, the above change occurs. On the other hand, in any of a case where the object22is added to the object queue20from the tail of the object queue20, a case where the object22is passing near the object queue20, and a case where the object is staying near the object queue20, the above change does not occur in the interval between the objects to be tracked in the object queue20. Accordingly, by considering the global behavior of the second object to be determined based on the relationship between the second object to be determined and the other object22included in the object queue20, whether or not the second object to be determined cuts in the object queue20can be accurately recognized.

In order to perform the cutting-in determination by considering the global behavior of the second object to be determined, the information processing apparatus2000of Example Embodiment 2 includes a second behavior inference unit2050and a second determination unit2060. The second behavior inference unit2050infers the global behavior of the second object to be determined. The second determination unit2060determines whether or not the second object to be determined cuts in the object queue20on the basis of the inferred global behavior of the second object to be determined.

<Example of Hardware Configuration>

For example, a hardware configuration of a computer that implements the information processing apparatus2000of Example Embodiment 2 is represented byFIG. 4in the same manner as Example Embodiment 1. However, the storage device1080of the computer1000implementing the information processing apparatus2000of the present example embodiment further stores a program module that implements the function of the information processing apparatus2000of the present example embodiment.

A summary of a flow of generating and updating the tracking information by the information processing apparatus2000of Example Embodiment 2 is represented inFIG. 6in the same manner as the case of the information processing apparatus2000of Example Embodiment 1.

FIG. 15is a flowchart illustrating a flow of process of updating the tracking information by the information processing apparatus2000of Example Embodiment 2. A flow of updating the tracking information by the information processing apparatus2000of Example Embodiment 2 is approximately the same as the flow of updating the tracking information by the information processing apparatus2000of Example Embodiment 1. The following two points are different.

First, the behavior inference unit2020of Example Embodiment 1 infers the global behavior of the first object to be determined in S208. On the other hand, the second behavior inference unit2050of Example Embodiment 2 infers the global behavior of the second object to be determined in S208.

Second,FIG. 8includes S210. On the other hand,FIG. 15includes S302. In S302, the second determination unit2060determines whether or not the second object to be determined cuts in the object queue20.

It should be noted that the information processing apparatus2000of Example Embodiment 2 may perform the leaving determination in addition to the cutting-in determination. In this case, the flowchart inFIG. 15includes S210before or after S302.

<Method of Deciding Object22Handled as Second Determination Object>

The information processing apparatus2000handles the object22that is present close to the object queue20and for which the associated object to be tracked is not present as the second object to be determined. There are various methods of determining whether or not the object22is present close to the object queue20. For example, in a case where the distance between the object22and the object queue20is less than or equal to a predetermined value, the information processing apparatus2000determines that the object22is present close to the object queue20. A method of computing the distance between the object22and the object queue20is described above. Besides, for example, in a case where the object22is positioned in the queue area, described above, the second behavior inference unit2050determines that the object22is present close to the object queue20.

The second behavior inference unit2050infers the global behavior of the second object to be determined (S208). In a case where the second object to be determined cuts in the object queue20, the interval between the objects to be tracked ahead and behind a position of cutting-in changes. Therefore, for example, the information processing apparatus2000infers the global behavior of the second object to be determined on the basis of the combination of the local behavior of the object and the local behavior of the other object to be tracked (for example, the object to be tracked positioned immediately ahead or behind) adjacent ahead or behind the object.

FIG. 16is a diagram illustrating a table showing the global behavior of the second object to be determined. It is assumed that the second object to be determined is the object A. InFIG. 16, the object B is an object that is positioned immediately ahead of the object A in the object queue20in a case where it is assumed that the object A is included in the object queue20. The object C is an object that is positioned immediately behind the object A in the object queue20in a case where it is assumed that the object A is included in the object queue20.

FIG. 16illustrates the global behavior of the object A (that is, the second object to be determined) in association with the combination of the local behaviors of the objects B and C. InFIG. 16, in a case where a combination of local states of the object B and the object C is a combination such that an interval between the object B and the object C is increased, a global state of the object A is set to a “cutting-in action”. In a case of other combinations, “staying or passing” is set.

The second determination unit2060performs the cutting-in determination for each second object to be determined (S302). Specifically, the second determination unit2060computes a likelihood of the second object to be determined cutting in the object queue20on the basis of the global behavior of the second object to be determined. The computed likelihood will be referred to as a cutting-in likelihood. The second determination unit2060determines whether or not the second object to be determined cuts in the object queue20on the basis of the cutting-in likelihood.

For example, in a case where the cutting-in likelihood computed for the second object to be determined is greater than or equal to a predetermined value, the second determination unit2060determines that the second object to be determined cuts in the object queue20. On the other hand, in a case where the cutting-in likelihood computed for the second object to be determined is less than the predetermined value, the second determination unit2060determines that the object to be determined does not cut in the object queue20.

Besides, for example, the second determination unit2060may determine that the second object to be determined cuts in the object queue20only in a case where a situation where the cutting-in likelihood of the second object to be determined is greater than or equal to the predetermined value continues for a predetermined period. Besides, for example, the second determination unit2060may compute a statistic value of the cutting-in likelihood of the second object to be determined in a predetermined period and determine that the second object to be determined cuts in the object queue20only in a case where the statistic value is greater than or equal to the predetermined value. For example, the statistic value is an average value, a cumulative value, a maximum value, or a minimum value.

In a case where the cutting-in likelihood is computed for the second determination object for the predetermined period, the information processing apparatus2000needs to also track the object22that is not checked as to being added to the object queue20. Therefore, for example, the information processing apparatus2000temporarily adds the object22(the object22handled as the second determination object) as a computation target of the cutting-in likelihood to the tracking information in an aspect in which the object22can be distinguished from the object to be tracked. After it is determined that the object22temporarily added to the tracking information cuts in the object queue20, the object22is handled as the object to be tracked.

The second determination unit2060computes the cutting-in likelihood using various parameters related to the second object to be determined. A function of outputting the cutting-in likelihood on the basis of the input parameters will be referred to as a cutting-in likelihood function. Types of parameters used by the cutting-in likelihood function will be described later.

The global behavior of the second object to be determined is reflected on the cutting-in likelihood obtained using the cutting-in likelihood function. A specific method thereof is the same as the method of reflecting the global behavior of the object to be determined on the leaving likelihood obtained using the leaving likelihood function.

Hereinafter, the leaving likelihood function will be further described with focus on the parameters used in the leaving likelihood function.

For example, the parameters used in the cutting-in likelihood function include a distance between the second object to be determined and the object to be tracked lining up immediately ahead of the second object to be determined, and a distance between the second object to be determined and the object to be tracked lining up immediately behind the second object to be determined. The “object to be tracked lining up immediately ahead of the second object to be determined” means the object to be tracked that is positioned immediately ahead of the second object to be determined in the object queue20in a case where it is assumed that the second object to be determined is included in the object queue20. Similarly, the “object to be tracked lining up immediately behind the second object to be determined” means the object to be tracked that is positioned immediately behind the second object to be determined in the object queue20in a case where it is assumed that the second object to be determined is included in the object queue20.

For example, a function that does not monotonically decrease along with an increase of the distance is used as the cutting-in likelihood function that uses the distance as a parameter.

Besides, for example, the parameters used in the cutting-in likelihood function include an angle between a movement direction of the second object to be determined and a movement direction of the object to be tracked. The movement direction of the object that is not lining up in the queue is irregular. On the other hand, the movement direction of the object lining up in the queue is usually forward of the queue. Accordingly, in a case where the second object to be determined is included in the object queue20, the angle between the movement directions of the second object to be determined and the object to be tracked is significantly small. For example, in the cutting-in likelihood function, the angle can be applied to any trigonometric function. Any object to be tracked can be used as the object to be tracked that is to be compared with the second object to be determined.

Besides, for example, the parameters used in the cutting-in likelihood function include a time-series change in movement direction of the second object to be determined. The second object to be determined cutting in the object queue20moves toward the queue line (in a direction orthogonal to the direction of the queue line) before cutting-in and moves on the queue line after cutting-in. Accordingly, for example, in a case where an angle between the second object to be determined and the queue line is applied to a sin function, a value gradually approaches 0 from a value close to 1. For example, in the cutting-in likelihood function, whether or not a change of this value is close to a general pattern of cutting-in can be used. As this general pattern, a great number of objects that cut in may be measured, and a model may be created.

Besides, for example, the parameters used in the cutting-in likelihood function include a staying time of the second object to be determined. In a case where the queue has low fluidity (proceeding takes a certain amount of time), a time in which the object stays at the same position is long. Accordingly, for example, a function that does not monotonically decrease along with an increase of the staying time is used as the cutting-in likelihood function that uses the staying time (for example, a time in which a state where the local state is “standstill” continues).

While example embodiments of the present invention have been described thus far with reference to the drawings, the example embodiments are illustrations of the present invention, and a configuration of combinations of the example embodiments or other various configurations can also be employed.