WO2010079556A1 - 移動体検出方法および移動体検出装置 - Google Patents

移動体検出方法および移動体検出装置 Download PDF

Info

Publication number
WO2010079556A1
WO2010079556A1 PCT/JP2009/006999 JP2009006999W WO2010079556A1 WO 2010079556 A1 WO2010079556 A1 WO 2010079556A1 JP 2009006999 W JP2009006999 W JP 2009006999W WO 2010079556 A1 WO2010079556 A1 WO 2010079556A1
Authority
WO
WIPO (PCT)
Prior art keywords
region
distance
region division
geodetic
inter
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2009/006999
Other languages
English (en)
French (fr)
Inventor
登一生
岩崎正宏
甲本亜矢子
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Corp
Original Assignee
Panasonic Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Panasonic Corp filed Critical Panasonic Corp
Priority to CN200980125394.0A priority Critical patent/CN102077250B/zh
Priority to US12/920,180 priority patent/US8213681B2/en
Priority to JP2010513554A priority patent/JP4542207B1/ja
Priority to EP09837446.5A priority patent/EP2378485B1/en
Publication of WO2010079556A1 publication Critical patent/WO2010079556A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/20—Analysis of motion
    • G06T7/215—Motion-based segmentation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/10—Image acquisition modality
    • G06T2207/10016—Video; Image sequence
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/30—Subject of image; Context of image processing
    • G06T2207/30196—Human being; Person
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/30—Subject of image; Context of image processing
    • G06T2207/30241—Trajectory

Definitions

  • the present invention relates to an image processing technique for detecting a moving body by extracting a region of the moving body in an image, and in particular, even when the moving body is a target that moves while changing its shape like a person,
  • the present invention relates to an apparatus for detecting a region of a moving body based on motion information in an image.
  • one mode of the moving object detection method is a method of detecting a moving object in a moving image by dividing all or part of the area of the moving object in the moving image.
  • FIGS. 8A and 8B are diagrams for explaining the characteristics of the geodesic distance.
  • FIGS. 9A to 9E are diagrams showing examples of clustering using geodetic distances.
  • FIGS. 10A to 10F are diagrams showing examples of the geodetic distance matrix, the representative geodetic distance matrix, and the reference matrix.
  • FIGS. 11A to 11D are diagrams showing examples of a representative geodetic distance matrix and a reference matrix.
  • FIG. 12 is a diagram illustrating an example of an image generated in the image output step.
  • FIG. 13 is a flowchart showing an operation procedure of the moving object detection device according to another embodiment of the present invention.
  • FIG. 14 is a flowchart showing an operation procedure of the moving object detection device according to the second embodiment of the present invention.
  • an image input step for receiving a plurality of pictures constituting a moving picture, and an image between two temporally adjacent pictures for each block composed of one or more pixels constituting the picture.
  • a motion analysis step of calculating a movement trajectory by connecting the detected motions with respect to the plurality of pictures, and in the distance calculation step, the movement trajectory calculated in the motion analysis step is calculated. You may acquire and calculate the said distance. With the configuration described above, it is possible to select a region extraction candidate without being affected by the local distance in the region candidate by selecting the region division candidate based on the inter-region geodetic distance between the region division candidates. Therefore, the region can be extracted more correctly.
  • an average value of Euclidean distances between the movement trajectories in the plurality of images is calculated as the distance representing the similarity between the movement trajectories. It is good.
  • a specific calculation method of the geodetic distance for example, in the geodetic distance calculation step, in the calculation of the geodetic distance from the first movement locus to the second movement locus, a plurality of pieces acquired in the distance calculation step are used.
  • the shortest route among all the routes that reach the second movement locus from the first movement locus with any one of the movement locus as a relay point is calculated as the geodetic distance, and more specifically, In the geodesic distance calculation step, (1) a non-linear distance is calculated by making a part of the distance between the movement trajectories calculated in the distance calculation step infinite, and (2) the nonlinear In calculating the geodetic distance from the first movement locus to the second movement locus based on the converted distance, the second movement locus is traced from the first movement locus using the other movement locus as a relay point. All The shortest distance among distances of the path preferably configured to calculate, as the geodesic distance.
  • An index representing the calculated distance between the two area division candidates an index representing variation in the area division candidates calculated from the sum of geodesic distances between a plurality of movement loci belonging to the certain area division candidate, and the other area It is more desirable that the value is normalized using an index representing variation in the region division candidate calculated from the sum of geodesic distances between a plurality of movement loci belonging to the division candidate.
  • the number of movement trajectories included in the area division candidates at least one area division candidate among the plurality of area division candidates generated in the area division candidate generation step belongs to one movement locus.
  • the inter-region geodesic distance calculation step as an inter-region geodesic distance between the region division candidate to which the one movement locus belongs and another region division candidate, any one of the one movement locus and the other region division candidates belonging to The structure which outputs geodesic distance with one movement locus
  • an output step may be included in which the moving image received in the image input step is subjected to image processing so as to have a different display mode for each region specified in the region dividing step and output.
  • the image processing is performed in a different display mode for each identified region, so that the detected moving object can be easily confirmed.
  • the movement trajectory representing the area is calculated from the movement trajectory constituting the area specified in the area dividing step, and the movement is predicted by predicting that the area moves according to the calculated representative movement trajectory.
  • a motion prediction step for predicting body motion may be included. Thereby, a motion can be predicted more accurately.
  • the moving body detection apparatus 100 acquires a moving image captured by the camera 110, detects a moving body in the acquired moving image, generates an image based on the detection result, and outputs the image.
  • the display 120 displays an image output from the moving object detection apparatus 100.
  • the motion analysis unit 102 detects image motion between two temporally adjacent pictures for each block composed of one or more pixels constituting a plurality of pictures received by the image input unit 101.
  • This is a processing unit that calculates a movement trajectory by linking detected motions for a plurality of pictures. That is, a block is a unit for calculating a movement locus, and is a collection of one or more pixels.
  • the distance between the blocks is changed by the movement, in particular, an object such as a person who moves while changing its shape like a joint object. It is possible to express movement as a distance matrix.
  • the movement locus of block i is referred to as movement locus i.
  • the “distance” in the present specification includes not only a distance between two points in a two-dimensional space but also an arithmetic distance between multi-dimensional data as described later, one value, or It is a set of multiple values (distance matrix).
  • the distance calculation unit 103 calculates, for example, an average value of Euclidean distances between movement trajectories in a plurality of images as a distance representing the similarity between the movement trajectories.
  • the geodetic distance calculation unit 106 and the region division candidate generation unit 107 constituting the region division unit 104 detect discontinuity in the distribution of the distance between the movement trajectories using the distance matrix calculated by the distance calculation unit 103, A plurality of region division candidates are generated in which movement trajectories separated by a distance smaller than the detected discontinuous point form one cluster.
  • the geodetic distance calculation unit 106 generates a plurality of threshold values that are determination criteria used for area division, and (1) sets the distance calculated by the distance calculation unit 103 for each of the generated threshold values. On the other hand, non-linearization is performed to make the distance larger than the threshold infinite, and (2) the geodesic distance between the movement trajectories in the plurality of movement trajectories calculated by the motion analysis unit 102 is calculated using the distance after the non-linearization. calculate.
  • the area division candidate generation unit 107 determines, as area division candidates, a collection of movement trajectories separated by a finite value of the geodetic distance based on the geodetic distances between the movement trajectories of the plurality of threshold values generated by the geodetic distance calculation unit 106. Thus, a plurality of area division candidates are generated.
  • the inter-region geodetic distance calculation unit 108 is configured to determine whether a plurality of region division candidates calculated by the region division candidate generation unit 107 is between two region division candidates based on a geodetic distance between a plurality of movement loci belonging to the region division candidate.
  • the inter-regional geodetic distance representing the degree of similarity is calculated.
  • the region division candidate selection unit 109 selects a region division candidate based on the inter-region geodetic distance calculated by the inter-region geodetic distance calculation unit 108, and performs clustering for each of the plurality of movement loci corresponding to the selected region division candidate. Thus, detection of a moving body in the image and area division of the image are performed.
  • the region division candidate selection unit 109 includes a condition in which the inter-region geodetic distance calculated by the inter-region geodetic distance calculation unit 108 among the region division candidates generated by the region division candidate generation unit 107 is predetermined. A region division candidate that satisfies the above is selected as a result of the region division.
  • area extraction includes both a detection technique for extracting an image area where a specific target object exists and an area division technique for dividing an image area for each object without distinguishing the target object. Yes. Note that the detection technique and the area division technique have many common parts, and therefore, they are not distinguished in this specification.
  • each component (the image input unit 101, the motion analysis unit 102, the distance calculation unit 103, the region division unit 104, and the output unit 105) included in the above-described moving body detection apparatus 100 is a program executed on a computer or the like. It may be realized by software, or may be realized by hardware such as an electronic circuit.
  • FIG. 2 is a diagram illustrating a hardware configuration of the moving object detection device according to the present embodiment realized by software.
  • the camera 110 captures and outputs an image
  • the computer 1002 acquires the image and performs region extraction processing to generate an image that displays the region extraction result.
  • the display 120 acquires and displays an image generated by the computer 1002.
  • a computer 1002 includes an I / F 1004, a CPU 1005, a ROM 1006, a RAM 1007, an HDD 1008, and a video card 1009.
  • a program for operating the computer 1002 is stored in the ROM 1006 or the HDD 1008 in advance.
  • the program is read from the ROM 1006 or the HDD 1008 to the RAM 1007 and expanded by the CPU 1005 which is a processor.
  • the CPU 1005 executes each coded instruction in the program expanded in the RAM 1007.
  • the I / F 1004 captures an image captured by the camera 110 into the RAM 1007 in accordance with the execution of the program.
  • the video card 1009 outputs an image generated according to the execution of the program and is displayed on the display 120.
  • FIG. 3 is a flowchart showing the operation of the moving object detection apparatus 100 of the present embodiment.
  • image input step S ⁇ b> 201 the image input unit 101 acquires a plurality of pictures constituting a moving image from the camera 110. Here, it is assumed that T pictures have been input.
  • FIG. 4 is a diagram illustrating an example of a shooting situation that is a situation of an object shot by the camera 110.
  • FIGS. 5A to 5F are diagrams showing an example of a plurality of pictures included in a moving image shot by the camera 110 in the shooting state of FIG.
  • the image input unit 101 receives T pictures from the first frame to the Tth frame from the camera 110. In the present embodiment, it is assumed that the number T of pictures is predetermined.
  • the motion analysis unit 102 calculates motion information between a plurality of inputted pictures, generates a movement locus, and outputs it.
  • a method for calculating the motion between a plurality of pictures here, with reference to I pixels on one picture of the plurality of pictures, the corresponding pixels in the other (T ⁇ 1) pictures are calculated.
  • Non-Patent Document 1 Anandan, “A Computational Framework and an Algorithm for the Measurement of Visual Motion”, International Journal of Computer Vision, Vol. 2, pp. 283-310, 1989
  • Non-Patent Document 2 Vladimir Kolmogorov and Ramin Zabih, “Computing Visual Correspondence with Occupation via Graph Cuts”, International Conference on Computer Vision 1, 200
  • T is the number of pictures used to calculate the movement trajectory.
  • the distance calculation unit 103 calculates a distance (in this case, an average value of the Euclidean distance) between the movement trajectories by inputting a plurality of movement trajectories.
  • the distance f (i, j) between the movement locus of the pixel i and the movement locus of the pixel j can be calculated by the following equation 2.
  • Equation 6 min (x, y) is a function that returns the smaller one of the value x and the value y.
  • s is a movement trajectory s, which is a relay point for tracing from the movement trajectory i to the movement trajectory j.
  • the relay point s in f ′ k (i, s) + f ′ k (s, j) is not limited to one point.
  • k corresponds to a plurality of threshold values R k .
  • the region division candidate generation unit 107 calculates an I ⁇ I geodetic distance matrix G expressed by the following equation 7. Generate k .
  • FIG. 7A shows the data distribution of the movement trajectory x shown in the above equation 1 as a two-dimensional data distribution for convenience of explanation.
  • each data point corresponds to the movement trajectory of the pixel i shown in Equation 1 above.
  • the relationship of the distance f (i, j) obtained by the above equation 2 is shown in FIG.
  • the distance between the data point i and the data point j is smaller than the distance between the data point i and the data point s.
  • FIGS. 8A and 8B show an example of the linear distance f (i, j).
  • the distance between the pixel i 502 at the head and the pixel j 503 at the hand is the distance indicated by the distance 501.
  • a geodetic distance is more suitable than a linear distance to extract the area of the mobile object based on the distance of the movement trajectory. It can be said that.
  • the threshold R k is set to a value between the maximum value and the minimum value of f (i, j) and a plurality of geodetic distance matrices are calculated, the number of different clusters of 1 or more and I or less from the geodetic distance matrix is calculated. It is possible to obtain clustering information, that is, candidates for moving object region extraction.
  • FIG. 9D An example shown in FIG. 9D will be described for clustering when the threshold value R k is set to a value between the maximum value and the minimum value of f (i, j).
  • FIG. 9B when the distance between the movement locus a and the movement locus b is f (a, b), it is assumed that f (d, e)> f (e, g).
  • the threshold value is set as R 1
  • the distance f (d, e) is than the threshold R 1 having a large value (i.e., f (d, e)> R1) and.
  • g 1 (d, e) becomes infinite even if the geodetic distance is obtained by the above equation 6 due to the non-linearization shown in the above equation 5.
  • the inter-regional geodetic distance calculation unit 108 performs information on the area division candidates generated in the area division candidate generation step S205, that is, K geodetic distance matrices g k ( i, j) and the corresponding cluster label ⁇ k m and the number of clusters M k are input, and the inter-region geodetic distance corresponding to the plurality of region division candidates is calculated.
  • the inter-region geodesic distance calculation unit 108 calculates the number of clusters M (M is 2 or more) from the geodesic distance matrix g k (i, j) corresponding to the K threshold values R k.
  • M is 2 or more
  • the geodesic distance matrix g k (i, j) corresponding to the K threshold values R k.
  • One is arbitrarily selected for each, and this is set as a representative geodetic distance matrix G M representing the number M of clusters.
  • the one having the largest threshold Rk is selected from a plurality of geodetic distance matrices having M clusters.
  • FIG. 10A is a diagram illustrating an example of a geodetic distance matrix G k obtained for K threshold values R k .
  • the geodetic distance matrix is an I ⁇ I geodetic distance matrix in which the geodetic distance g k (i, j) of the movement locus is an element of i rows and j columns.
  • Figure 10 (b) ⁇ FIG 10 (d) are diagrams showing an example of a representative geodesic distance matrix G M clusters C 1-3.
  • the movement trajectories corresponding to the rows and columns of the representative geodetic distance matrixes of FIGS. 10B to 10D are all common.
  • FIG. 10 (b) and FIG. 9 (c), FIG. 10 (c) and FIG. 9 (d), FIG. 10 (d) and FIG. 9 (e) are representative geodesic distances when the number of clusters is 1 to 3, respectively. It is a conceptual diagram of the high-dimensional space of the distance of a matrix and a movement locus.
  • FIG. 11B the reference matrix clusters corresponding to the clusters ⁇ 1 2 and ⁇ 2 2 of the representative geodetic distance matrix are denoted by ⁇ 1 2 and ⁇ 2 2 (two hatched areas shown in FIG. 11B).
  • an element region two vertical line regions in FIG. 11B) whose value is infinite in the representative geodetic distance matrix and whose value is finite in the reference matrix is defined as ⁇ 1,2 2 . .
  • the inter-regional geodetic distance calculation unit 108 calculates the inter-regional geodetic distance that is an index of the distance between the clusters. To do.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Image Analysis (AREA)
  • Image Processing (AREA)
  • Studio Devices (AREA)

Abstract

移動体の形状・大きさの変化、遮蔽の影響を受けずに、正しく領域を抽出することができる移動体検出方法であって、動画像を構成する複数のブロックのそれぞれにおける画像の移動軌跡間の類似度を表す距離を算出し（Ｓ２０３）、その距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定する（Ｓ２０９）。ステップＳ２０９では、複数の閾値のそれぞれについて、（１）上記距離を非線形化し、（２）非線形化後の距離から複数の移動軌跡の間の測地距離を算出し（Ｓ２０４）、（３）複数の移動軌跡のうち有限の値の測地距離だけ離れた移動軌跡の集まりを領域分割候補とし（Ｓ２０５）、それら領域分割候補について領域分割候補間の類似度を表す尺度である領域間測地距離を算出し（Ｓ２０６）、それら領域分割候補のうち、領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する（Ｓ２０７）。

Description

移動体検出方法および移動体検出装置
　本発明は、画像中の移動体の領域を抽出することによって移動体を検出する画像処理技術に関し、特に、移動体が人物のように形状が変化しながら移動する対象である場合においても、動画像中の動き情報に基づいて移動体の領域を検出する装置に関するものである。
　従来より、移動体の像（以下、単に「移動体」という。）が含まれる画像から、画像中の移動体の領域を抽出することによって移動体を検出する領域抽出技術の研究開発が広く行われてきている。特に移動体が人である場合にその移動体の領域を抽出する技術は、デジタルビデオカメラもしくはデジタルスチルカメラにおける焦点制御、画質改善処理、自動車の安全運転支援システム、または、ロボットにおける人との衝突回避制御もしくは衝突回避のための警報などに、共通して利用される基礎技術である。
　画像中の移動体の領域を抽出する技術のうち、一般的な手法として、（１）あらかじめ用意した移動体のモデルと、画像中の候補領域との類似度を評価して移動体の領域を特定する方法と、（２）画像を複数の小領域に分割して特徴量を算出し、特徴量を基準として類似する領域を統合することで移動体の領域を特定する方法の２つ手法がある。
　前者の代表的な手法として、画像から移動体領域の候補を抽出したのち、抽出した移動体領域の候補とあらかじめ用意した移動体モデルとの類似度を評価して、類似度が高い領域を移動体領域として抽出する手法がある。さらに、歩行する人物等のように、形状が変化しながら移動する移動体の領域を抽出する場合、形状の変化を考慮した移動体モデルを利用する手法がある。
　例えば、特許文献１に記載の手法では、移動体領域候補として複数の画像から移動体のシルエット画像を抽出する。そして、あらかじめパラメータ化した移動体の形状の変化に関するモデルと、抽出したシルエット画像との類似度を評価し、類似度が高い領域とモデルのパラメータを推定する手法が開示されている。これによって、形状が変化しながら移動する人物に対しても、パラメータ化したモデルを当てはめることができるため、移動体の領域抽出を可能にしている。
　後者の代表的な手法としては、画像を複数の小領域に一旦分割し、各小領域の画素の輝度値に基づいた特徴量を抽出したのち、複数の小領域間の特徴量の類似度を評価して、類似度が高い領域を同一の移動体領域として統合する手法がある。
　例えば、特許文献２に記載の手法では、画像を矩形の小領域に一旦分割し、小領域の輝度や動きに基づいて特徴量を算出し、特徴量の類似度の順番に基づいて小領域を統合することで、移動体の領域抽出を可能にしている。
特開平８－２１４２８９号公報 特開２００６－０３１１１４号公報
　しかしながら、上記した従来の領域抽出の技術は、例えば、街頭などで複数の人物等の移動体が行き交うシーンなどのように、移動体が他の移動体によって部分的に遮蔽される場合、あるいは移動体の大きさが著しく異なる移動体を含む場合などに、正しく移動体を抽出することができないという問題がある。
　特許文献１に記載の手法に代表される、あらかじめ用意したモデルを用いる従来の領域抽出手法では、画像から移動体領域の候補を抽出する必要がある。この時、適切に移動体領域候補を抽出できなければ、移動体をパラメータ化したモデルを正確に移動体領域の候補に当てはめることが不可能になる。特に、上述のようなシーンにおいては、移動体の形状あるいは大きさが大きく変化するため、移動体領域の候補を適切に抽出することは困難である。
　さらに、移動体領域の候補を適切に抽出できたとしても以下のような課題がある。特に人物等の多関節物体が移動体である場合、移動体のさまざまな姿勢あるいは大きさに起因する画像上の形状あるいは大きさの変化の幅が非常に大きいため、移動体モデルのパラメータ化を行う際に膨大な数のパラメータが必要となる。このことは、モデルの当てはめ誤りを誘発する。そのため、例えば、複数の移動体を１つの移動体として誤って領域抽出したり、抽出対象となる移動体が存在しない領域を移動体として誤って領域抽出したりするなど、正しく移動体を検出することができないという課題がある。
　特許文献２に記載の手法に代表される、小領域間の特徴量を用いる従来の領域抽出手法では、特徴量として用いる輝度値あるいは動きが類似していない２つの小領域は、異なる２つの移動体に属する領域として分離抽出される。そのため、ある移動体が、人物のように場所によって輝度値が異なり、かつ、場所によって動きが異なる場合、同一移動体の上の２つの小領域であっても、異なる２つの移動体に属する領域として誤って分離抽出されてしまうため、正しく移動体を検出することができないという課題がある。
　そこで、本発明は、上記従来の課題を解決するためになされたものであり、動画像中における移動体の形状の変化、大きさの変化、又は遮蔽などの影響を受けずに、移動体の領域を正しく抽出することができる移動体検出方法等を提供することを目的とする。
　上記目的を達成するために、本発明に係る移動体検出方法の一形態は、動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する方法であって、動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出ステップと、前記距離算出ステップで算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割ステップとを含み、前記領域分割ステップは、前記距離算出ステップで算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出ステップと、前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成ステップと、前記領域分割候補生成ステップで生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出ステップと、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択ステップとを含む。
　上記した構成によって、領域分割候補間の領域間測地距離に基づいて領域分割候補を選択することで、領域候補内の局所的な距離の影響を受けることなく領域抽出の候補を選択することが可能になるため、より正しく領域抽出することができる。つまり、移動軌跡が類似する画像の領域がまとめられて領域分割候補になること、領域分割候補の選択においては領域分割候補間の類似度が判断されること、及び、領域分割候補間の類似度については移動軌跡間の測地距離に基づいて定義される領域間測地距離で判断されることから、類似する動きをもつ画像の領域が正確に抽出されるので、移動体が他の移動体によって部分的に遮蔽される場合、あるいは移動体の大きさが著しく異なる移動体を含む場合などであっても正しく移動体が抽出されるとともに、ある移動体が人物のように場所によって輝度値が異なり、かつ、場所によって動きが異なる場合であっても、同一移動体の上の２つの小領域が異なる２つの移動体に属する領域として誤って分離抽出されてしまうことが回避される。
　なお、本発明の移動体検出方法は、コンピュータ上のプログラムによって実現されるだけでなく、上記各ステップをハードウェアによって構成した移動体検出装置、上記各ステップをコンピュータに実行させるプログラム、そのプログラムを格納したＣＤ－ＲＯＭ等のコンピュータ読み取り可能な記録媒体、動画像において動きをもつオブジェクトの領域を抽出、あるいは、分割する画像処理装置等として実現することもできる。
　上記の方法及び装置等により、２つの領域分割候補の移動軌跡間の測地距離に基づいて領域分割をすることができるので、動画像中における移動体の形状の変化、大きさの変化、又は遮蔽などの影響を受けずに、移動体の領域を正しく抽出することが可能となる。さらに、領域抽出を行った結果を用いて、移動体の移動予測を行うこともできる。
　よって、デジタルビデオカメラ等の動画像撮影装置が普及してきた今日において、デジタルカメラの焦点制御や画質改善処理、自動車の安全運転支援システム、ロボットにおける人との衝突回避制御や警報などへの応用技術として、本発明の実用価値は極めて高い。
図１は、本発明の実施の形態１における移動体検出装置の構成を示す図である。 図２は、コンピュータによって構成された移動体検出装置のハードウェア構成を示す図である。 図３は、本発明の実施の形態１における移動体検出装置の動作の手順を示すフローチャートである。 図４は、本発明の実施の形態における撮影状況の例を示す図である。 図５（ａ）～（ｆ）は、本発明の実施の形態における入力動画像を構成する複数のピクチャの例を示す図である。 図６は、移動軌跡の例を示す図である。 図７（ａ）～（ｃ）は、測地距離の算出手順を示す概念図である。 図８（ａ）及び（ｂ）は、測地距離の特徴を説明する図である。 図９（ａ）～（ｅ）は、測地距離を用いたクラスタリングの例を示す図である。 図１０（ａ）～（ｆ）は、測地距離マトリクス、代表測地距離マトリクス及び参照マトリクスの例を示す図である。 図１１（ａ）～（ｄ）は、代表測地距離マトリクス及び参照マトリクスの例を示す図である。 図１２は、画像出力ステップで生成した画像の例を示す図である。 図１３は、本発明に係る別の形態における移動体検出装置の動作の手順を示すフローチャートである。 図１４は、本発明の実施の形態２における移動体検出装置の動作の手順を示すフローチャートである。 図１５（ａ）～（ｄ）は、本発明の実施の形態２における領域分割候補の例を示す図である。 図１６（ａ）～（ｄ）は、（ａ）は移動軌跡の例を示し、（ｂ）は移動軌跡のクラスタリングの例を示し、（ｃ）及び（ｄ）は領域抽出結果を示す図である。 図１７（ａ）及び（ｂ）は、領域間測地距離を用いて領域分割することの効果を説明する図である。 図１８は、本発明に係る更に別の形態における移動体検出装置による動き予測を説明する図である。
　本発明の一実施形態は、動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する方法であって、動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出ステップと、前記距離算出ステップで算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割ステップとを含み、前記領域分割ステップは、前記距離算出ステップで算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出ステップと、前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成ステップと、前記領域分割候補生成ステップで生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出ステップと、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択ステップとを含む構成としたものである。
　ここで、さらに、動画像を構成する複数枚のピクチャを受け付ける画像入力ステップと、前記ピクチャを構成する１個以上の画素からなるブロックごとに、時間的に隣接する２枚のピクチャ間での画像の動きを検出し、検出した動きを前記複数枚のピクチャについて連結することで、移動軌跡を算出する動き解析ステップとを含み、前記距離算出ステップでは、前記動き解析ステップで算出された移動軌跡を取得し、前記距離を算出してもよい。上記した構成によって、領域分割候補間の領域間測地距離に基づいて領域分割候補を選択することで、領域候補内の局所的な距離の影響を受けることなく領域抽出の候補を選択することが可能になるため、より正しく領域抽出することができる。
　なお、移動軌跡間の距離の算出方法として、例えば、前記距離算出ステップでは、移動軌跡間の類似度を表す前記距離として、前記複数の画像における移動軌跡間のユークリッド距離の平均値を算出する構成としてもよい。また、測地距離の具体的な算出方法として、例えば、前記測地距離算出ステップでは、第１の移動軌跡から第２の移動軌跡までの測地距離の算出においては、前記距離算出ステップで取得された複数の移動軌跡のいずれかを中継点として前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路のうちの最短の経路を、前記測地距離として算出し、より具体的には、前記測地距離算出ステップでは、（１）前記距離算出ステップで算出された移動軌跡間の距離に対して、その一部を無限大化することで非線形化した距離を算出し、（２）前記非線形化した距離に基づいた、第１の移動軌跡から第２の移動軌跡までの測地距離の算出において、他の移動軌跡を中継点として、前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路の距離うちの最短の距離を、前記測地距離として算出する構成とするのが好ましい。
　ここで、領域分割候補の生成方法として、前記測地距離算出ステップでは、複数の閾値を取得し、取得した複数の閾値を、移動軌跡の近傍を定義する閾値として用いて、前記距離算出ステップで算出された移動軌跡間の距離から、それぞれの閾値ごとに、近傍にある移動軌跡を辿っていく経路における距離を算出することで、前記移動軌跡間の測地距離を算出し、前記領域分割候補生成ステップでは、前記測地距離算出ステップで算出した複数の閾値ごとの移動軌跡間の測地距離に基づいて、類似する移動軌跡の集まりを１つの領域分割候補とすることで、前記複数の領域分割候補を生成する構成としてもよい。このとき、複数の閾値の具体例として、前記測地距離算出ステップでは、前記複数の閾値として、前記距離算出ステップで算出された複数の距離のうちの最大値と最小値との間の値を生成するのが好ましい。これによって、閾値の候補を限定することで、より高速に領域抽出することができる。
　また、領域間測地距離の算出方法として、前記領域間測地距離算出ステップでは、前記複数の閾値のそれぞれに対して前記領域分割候補生成ステップで生成された複数の領域分割候補のセットのうちの第１の領域分割候補のセットにおける２つの領域分割候補間の領域間測地距離として、当該２つの領域分割候補における測地距離である代表測地距離と、当該第１の領域分割候補のセットに含まれる領域分割候補の総数よりも次に小さい総数だけ領域分割候補が含まれる第２の領域分割候補のセットにおける測地距離である参照測地距離とを用いて、予め定められた演算をすることで算出する。より具体的には、前記領域間測地距離算出ステップでは、前記参照測地距離と前記代表測地距離とに基づいて、２つの領域分割候補間の距離を表す指標と、各領域分割候補内のばらつきを表す指標とを算出し、前記距離を表す指標を、前記ばらつきを表す指標で正規化する演算をすることで、前記領域間測地距離を算出する。または、前記領域間測地距離算出ステップで算出される領域間測地距離は、ある領域分割候補に属する複数の移動軌跡と他の領域分割候補に属する複数の移動軌跡との間の測地距離の総和から算出した２つの領域分割候補間の距離を表す指標を、前記ある領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標と、前記他の領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標とを用いて、正規化した値であるのが更に望ましい。上記した構成によって、領域分割候補間の距離をより正しく反映した領域間測地距離の算出が可能になるため、移動体をより正しく領域抽出することができる。
　ここで、領域分割候補の選択基準として、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力する構成としてもよい。これにより、領域間測地距離が大きく離れた領域分割候補が選択されるので、動きが大きく異なる画像の領域が分離され、移動体あるいは移動体の部位が正確に領域抽出される。
　また、領域分割候補の別の選択基準として、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、前記領域分割候補を選択し、前記領域分割の結果として出力するのが好ましい。具体的には、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より大きい２つの領域分割候補を、異なる領域として選択し、前記領域分割の結果として出力したり、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より小さい２つの領域分割候補を、同一の領域として選択し、前記領域分割の結果として出力したり、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、（１）大きいほど２つの領域分割候補は異なる領域となるように、かつ、（２）小さいほど２つの領域分割候補を同一の領域となるように領域分割候補を選択し、前記領域分割の結果として出力したり、前記距離算出ステップ及び前記領域分割ステップが、新たな動画像について、繰り返し実行され、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記繰り返し実行において前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力したりするのが好ましい。
　上記した構成によって、領域間測地距離の時間変化に基づいて領域分割候補を選択することで、ある領域分割候補と異なる動きをする領域分割候補を選択することが可能になるため、移動体をより正しく領域抽出することができる。
　また、領域分割候補の別の生成方法として、前記領域分割候補生成ステップでは、前記画像入力ステップで取得した画像の輝度情報に基づいて、複数の領域分割候補画像を生成し、領域分割候補画像に対応する１つ以上の移動軌跡の集まりを領域分割候補とすることで、前記複数の領域分割候補を生成する構成としてもよい。これにより、画像の輝度情報に基づいて領域分割候補が生成されるので、輝度上で類似する画像の領域が一つの領域として領域分割されることとなり、領域分割の精度が向上する。
　また、領域分割候補の含まれる移動軌跡の数として、前記領域分割候補生成ステップで生成される複数の領域分割候補のうち、少なくとも１つの領域分割候補は１個の移動軌跡が属するものであり、前記領域間測地距離算出ステップでは、前記１個の移動軌跡が属する領域分割候補と他の領域分割候補との領域間測地距離として、前記１個の移動軌跡と前記他の領域分割候補に属する任意の１つの移動軌跡との測地距離を出力する構成であってもよい。
　このとき、領域分割候補の生成方法として、前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より小さい２つの移動軌跡を、同じ領域として特定する構成であってもよいし、前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より大きい２つの移動軌跡を、異なる領域として特定する構成であってもよい。これにより、１つの領域分割候補に１個の移動軌跡だけが含まれる場合であっても適切に領域間測地距離が算出されるとともに、測地距離の時間変化に依存した適切な領域分割候補が生成され、移動体が正しく領域抽出される。
　また、さらに、前記画像入力ステップで受け付けた動画像に対して、前記領域分割ステップで特定された領域ごとに異なる表示態様となるように、画像処理を施し、出力する出力ステップを含んでもよい。これによって、特定された領域ごとに異なる表示態様で画像処理が施されるので、検出された移動体を容易に確認することができる。
　また、さらに、前記領域分割ステップで特定された領域を構成する移動軌跡から、当該領域を代表する移動軌跡を算出し、算出した代表の移動軌跡に従って当該領域が移動すると予測することで、前記移動体の動きを予測する動き予測ステップを含んでもよい。これにより、より精度良く動きを予測することができる。
　以下、本発明の実施の形態について、図面を用いて説明する。
　（実施の形態１）
　図１は、実施の形態１における移動体検出装置１００の構成を示す図である。図１に示されるように、この移動体検出装置１００は、画像入力部１０１、動き解析部１０２、距離算出部１０３、領域分割部１０４、及び出力部１０５を備える。ここで、領域分割部１０４は、測地距離算出部１０６、領域分割候補生成部１０７、領域間測地距離算出部１０８、及び領域分割候補選択部１０９を備える。移動体検出装置１００は、複数枚のピクチャを含む動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する装置である。本実施の形態では、移動体検出装置１００は、カメラ１１０で撮影した動画像を取得し、取得した動画像中の移動体を検出し、検出結果に基づいて画像を生成して出力する。ディスプレイ１２０は、移動体検出装置１００から出力される画像を表示する。
　画像入力部１０１は、カメラ１１０等から送られてくる、動画像を構成する時間的に異なる複数枚のピクチャの入力を受け付ける処理部であり、例えば、ビデオカメラ、あるいは、ビデオカメラと接続された通信インターフェース等である。
　動き解析部１０２は、画像入力部１０１で受け付けられた複数枚のピクチャを構成する１個以上の画素からなるブロックごとに、時間的に隣接する２枚のピクチャ間での画像の動きを検出し、検出した動きを複数枚のピクチャについて連結することで、移動軌跡を算出する処理部である。つまり、ブロックとは、移動軌跡を算出する単位であり、１個以上の画素の集まりである。
　距離算出部１０３は、動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する処理部であり、本実施の形態では、移動する物体の形状変化を捉えるために、動き解析部１０２で算出したブロックiの移動軌跡と、i以外のブロックの移動軌跡とを用いて、ブロックの動きの類似度を表す距離を算出する。よって、Ｉ個のブロックの移動軌跡を用いた場合、算出される距離はＩ行Ｉ列（Ｉ×Ｉ）の距離マトリクスとなる。ここでは、ブロックの動きの類似度を評価する距離を計算することによって、ブロック間の距離が動きによって変化する移動体、特に、関節物体のように形状が変化しながら移動する人物等の物体の動きを距離マトリクスとして表現することが可能である。なお、以降の説明では、ブロックiの移動軌跡を移動軌跡iと呼ぶこととする。このように、本明細書における「距離」は、２次元空間における２点間の距離だけでなく、後述するように、多次元のデータ間の算術的な距離を含み、１つの値、あるいは、複数の値の集合（距離マトリクス）である。なお、距離算出部１０３は、移動軌跡間の類似度を表す距離として、例えば、複数の画像における移動軌跡間のユークリッド距離の平均値を算出する。
　領域分割部１０４は、距離算出部１０３で算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする処理部である。この領域分割部１０４は、測地距離算出部１０６、領域分割候補生成部１０７、領域間測地距離算出部１０８及び領域分割候補選択部１０９を有する。
　領域分割部１０４を構成する、測地距離算出部１０６および領域分割候補生成部１０７は、距離算出部１０３で算出した距離マトリクスを用いて、移動軌跡間の距離の分布における不連続性を検出し、検出した不連続点よりも小さい距離だけ離れた移動軌跡同士が一つのクラスタとなる領域分割候補を複数生成する。
　具体的には、測地距離算出部１０６は、領域分割に用いられる判断基準である複数の閾値を生成し、生成した複数の閾値のそれぞれについて、（１）距離算出部１０３で算出された距離に対して、当該閾値よりも大きい距離を無限大化する非線形化を施し、（２）非線形化後の距離を用いて、動き解析部１０２が算出した複数の移動軌跡における移動軌跡間の測地距離を算出する。
　領域分割候補生成部１０７は、測地距離算出部１０６で生成した複数の閾値のそれぞれの移動軌跡間の測地距離に基づいて、有限の値の測地距離だけ離れた移動軌跡の集まりを領域分割候補とすることで、複数の領域分割候補を生成する。
　領域間測地距離算出部１０８は、領域分割候補生成部１０７で算出した複数の領域分割候補に対して、領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、２つ領域分割候補間の類似度を表す領域間測地距離を算出する。
　領域分割候補選択部１０９は、領域間測地距離算出部１０８で算出された領域間測地距離をもとに領域分割候補を選択し、選択した領域分割候補に対応する複数の移動軌跡ごとにクラスタリングすることによって、画像中の移動体の検出と画像の領域分割を行う。具体的には、領域分割候補選択部１０９は、領域分割候補生成部１０７で生成された領域分割候補のうち、領域間測地距離算出部１０８で算出された領域間測地距離が予め定められた条件を満たす領域分割候補を、領域分割の結果として選択する。
　出力部１０５は、領域分割部１０４で行った動画像中の移動体の検出結果もしくは、画像の領域分割結果を出力する。具体的には、出力部１０５は、画像入力部１０１で受け付けた動画像に対して、例えば、領域分割部１０４で特定された領域ごとに異なる表示態様となるように、画像処理を施し、ディスプレイ１２０等に出力する。
　本明細書において、「領域抽出」とは、ある特定の対象物が存在する画像領域を抽出する検出技術と、対象物の区別なく物体ごとに画像領域を分割する領域分割技術の両者を含んでいる。なお、検出技術と領域分割技術とは、共通する部分が多いため、本明細書においては両者を区別しない。
　なお、上記した移動体検出装置１００を構成する各構成要素（画像入力部１０１、動き解析部１０２、距離算出部１０３、領域分割部１０４、出力部１０５）は、コンピュータ上で実行されるプログラム等のソフトウェアで実現されてもよいし、電子回路等のハードウェアで実現されてもよい。
図２は、ソフトウェアによって実現された本実施の形態における移動体検出装置のハードウェア構成を示す図である。図２において、カメラ１１０は画像を撮影して出力し、コンピュータ１００２は画像を取得して領域抽出処理を行って、領域抽出結果を表示する画像を生成する。ディスプレイ１２０はコンピュータ１００２で生成された画像を取得して表示する。コンピュータ１００２は、Ｉ／Ｆ１００４、ＣＰＵ１００５、ＲＯＭ１００６、ＲＡＭ１００７、ＨＤＤ１００８、ビデオカード１００９で構成される。コンピュータ１００２を動作させるプログラムは、ＲＯＭ１００６またはＨＤＤ１００８にあらかじめ保持されている。プログラムは、プロセッサであるＣＰＵ１００５によって、ＲＯＭ１００６またはＨＤＤ１００８からＲＡＭ１００７に読み出されて展開される。ＣＰＵ１００５はＲＡＭ１００７に展開されたプログラム中のコード化された各命令を実行する。Ｉ／Ｆ１００４は、プログラムの実行に応じて、カメラ１１０で撮影された画像を、ＲＡＭ１００７へ取り込む。ビデオカード１００９は、プログラムの実行に応じて生成された画像を出力し、ディスプレイ１２０で表示される。
　なお、コンピュータプログラムは、半導体であるＲＯＭ１００６またはＨＤＤ１００８に格納されるのに限られず、たとえば光ディスクに格納されていてもよい。また、コンピュータプログラムは、有線や無線のネットワーク、放送などを介して伝送され、コンピュータのＲＡＭ１００７に取り込まれてもよい。
　以下、本実施の形態の移動体検出装置１００の動作を、図３を用いて説明する。
　図３は、本実施の形態の移動体検出装置１００の動作を表すフローチャートである。
　図３において、７つのステップＳ２０１～Ｓ２０９は、それぞれ図１の各処理部に対応している。すわなち、画像入力部１０１は画像入力ステップＳ２０１、動き解析部１０２は動き解析ステップＳ２０２、距離算出部１０３は距離算出ステップＳ２０３、測地距離算出部１０６は測地距離算出ステップＳ２０４、領域分割候補生成部１０７は領域分割候補生成ステップＳ２０５、領域間測地距離算出部１０８は領域間測地距離算出ステップＳ２０６、領域分割候補選択部１０９は領域分割候補選択ステップＳ２０７、出力部１０５は画像出力ステップＳ２０８の各動作を実行する。領域分割部１０４は、領域分割ステップＳ２０９を実行する。
　画像入力ステップＳ２０１において、画像入力部１０１は、カメラ１１０から、動画像を構成する複数のピクチャを取得する。ここではＴ枚のピクチャが入力されたものとする。
　図４は、カメラ１１０によって撮影される対象物の状況である撮影状況の一例を示す図である。また、図５（ａ）～図５（ｆ）は、カメラ１１０によって、図４の撮影状況において撮影された動画像に含まれる複数枚のピクチャの一例を示す図である。画像入力部１０１は、第１フレームから第ＴフレームまでのＴ枚のピクチャをカメラ１１０から受け付ける。本実施の形態では、ピクチャの数Ｔは、あらかじめ定められているものとする。
　次に、動き解析ステップＳ２０２では、動き解析部１０２は、入力された複数のピクチャ間の動き情報を算出し、移動軌跡を生成して出力する。複数のピクチャ間の動きを算出する手法として、ここでは複数のピクチャのうちのある１つのピクチャ上のＩ個の画素を基準に、他の（Ｔ－１）枚のピクチャ中の対応する画素を探索する。なお、Ｉ個の画素の代わりに、Ｉ個の小矩形領域（ブロック）を基準にしても良い。例えば、ｔフレームと（ｔ＋１）フレームのピクチャを用いて、ｔフレームのピクチャ上の画素iの画素座標(xit,yit) (i=1…Ｉ)に対応する、（ｔ＋１）フレームのピクチャ上の画素座標(xit+1，yit+1)を推定する。ピクチャが３枚以上ある場合は、順次対応する座標を求めていくことで、入力したＴ枚全てのピクチャのＩ個の対応点を算出する。
　上記した複数のピクチャ間の対応点を算出する具体的な手法は、非特許文献１もしくは非特許文献２などに詳しく記載されているため、ここでは詳細の説明を省略する。
（非特許文献１）Ｐ．Ａｎａｎｄａｎ，“Ａ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｆｒａｍｅｗｏｒｋ　ａｎｄ　ａｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　Ｍｅａｓｕｒｅｍｅｎｔ　ｏｆ　Ｖｉｓｕａｌ　Ｍｏｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ，Ｖｏｌ．２，ｐｐ．２８３－３１０，１９８９
（非特許文献２）Ｖｌａｄｉｍｉｒ　Ｋｏｌｍｏｇｏｒｏｖ　ａｎｄ　Ｒａｍｉｎ　Ｚａｂｉｈ，“Ｃｏｍｐｕｔｉｎｇ　Ｖｉｓｕａｌ　Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ　ｗｉｔｈ　Ｏｃｃｌｕｓｉｏｎｓ　ｖｉａ　Ｇｒａｐｈ　Ｃｕｔｓ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ，２００１
　そして、この動き解析ステップＳ２０２では、動き解析部１０２は、Ｉ個の画素のＴ枚のピクチャにわたる動き情報である、対応点の画素座標の組から、Ｉ個の画素ごとに対応する移動軌跡を、下記式１のように、Ｉ個生成する。
Figure JPOXMLDOC01-appb-M000001
　ここで、Ｔは移動軌跡の算出に用いたピクチャの枚数である。
　図６は、移動軌跡xの例を示す図である。移動軌跡xは、時刻ｔから時刻ｔ+(Ｔ-1)の入力画像３０１において、画素i３０３に対応する他のピクチャ上へ動き情報３０２から算出した、画素座標の集まりからなるベクトルである。
　次に、距離算出ステップＳ２０３にて、距離算出部１０３は、複数の移動軌跡を入力として移動軌跡間の距離（ここでは、ユークリッド距離の平均値）を算出する。画素iの移動軌跡と画素ｊの移動軌跡との距離f(i,j)は、下記式２により算出できる。
Figure JPOXMLDOC01-appb-M000002
　なお、本実施の形態において、後述する測地距離ｇと区別して説明するために、移動軌跡間の距離ｆを線形距離と呼ぶが、線形距離の定義式を線形演算に限定するものではなく、線形距離の定義式に非線形の演算が含まれていても良い。
　なお、線形距離f(i,j)を算出する式として、上記式２の代わりに下記式３を用いてもよい。
Figure JPOXMLDOC01-appb-M000003
　ここで、wは重み係数であり、設計者が設定するパラメータである。上記式３の移動軌跡間の距離f(i,j)は、移動軌跡間距離の時間平均値ptnijに、移動軌跡間距離の時間変動成分mtnijを加えたものである。特に移動軌跡間距離の時間変動成分mtnijは、画素の動きの類似度を示すものであり、これによって、画素間のなす距離の関係が時間的に変化しない剛体だけでなく、関節物体等の形状変化を捉えることができる。
　そして、距離算出部１０３は、上記式２または上記式３で算出した、Ｉ個の移動軌跡間の距離f(i,j)から、下記式４に示されるＩ×Ｉの距離マトリクスＦを生成する。
Figure JPOXMLDOC01-appb-M000004
　続いて、測地距離算出ステップＳ２０４では、移動軌跡間の距離の集まりである距離マトリクスＦを取得して、移動軌跡の近傍を定義する距離の閾値Ｒを複数用いて、前記移動軌跡間の距離を測地距離に変換する。つまり、測地距離算出ステップＳ２０４では、複数の閾値を取得し、取得した複数の閾値を、移動軌跡の近傍を定義する閾値として用いて、距離算出ステップＳ２０３で算出された移動軌跡間の距離から、それぞれの閾値ごとに、近傍にある移動軌跡を辿っていく経路における距離を算出することで、移動軌跡間の測地距離を算出する。そして、移動軌跡間の測地距離が有限である移動軌跡の集まりの情報を含む領域分割候補を複数生成して出力する。
　以降、測地距離算出ステップＳ２０４の動作をさらに詳しく説明する。
　まず、測地距離算出ステップＳ２０４では、測地距離算出部１０６は、上記式２で算出した距離f(i,j)に対してあらかじめ定められたＫ個の閾値Ｒkを用いて、それぞれの閾値に対して、下記式５の非線形化処理を行い、f´k(i,j)を算出する。
Figure JPOXMLDOC01-appb-M000005
　次に、測地距離算出部１０６は、非線形化された距離f´k(i,j)を用いて、測地距離を算出する。測地距離とは、複数の点を結ぶノードの距離（長さ）が得られているときに、ある２点間を結び得る全ての経路の距離のうちの最短の距離である。よって、測地距離算出部１０６は、第１の移動軌跡から第２の移動軌跡までの測地距離の算出においては、距離算出部１０３で算出された複数の移動軌跡のいずれかを中継点として第１の移動軌跡から第２の移動軌跡に辿りつく全ての経路のうちの最短の経路を、測地距離として、算出する。
　例えば、移動軌跡ｉと移動軌跡ｊの２点間を直接結ぶノードの距離f´k(i,j)が得られているとする。このとき移動軌跡iと移動軌跡jの２点間を結ぶ経路は、２点間を直接結ぶノード以外に、別の移動軌跡ｓをたどる経路もある。この経路の距離をf´k(i,s)+ f´k(s,j)とする。このような複数の経路の距離のうちで、最も短い距離を、下記式６に示されるように、測地距離gk(i,j)とする。
Figure JPOXMLDOC01-appb-M000006
　上記式６において、min（ｘ，ｙ）は、値ｘと値ｙのうち小さい方を返す関数である。また、ｓは、移動軌跡ｓであり、移動軌跡iから移動軌跡jに辿（たど）りつくための中継点である。ここで、f´k(i,s)+ f´k(s,j)における中継点ｓは１点に限るものではない。なお、ｋは複数の閾値Ｒkに対応する。
　上述した多次元データ間の測地距離を算出する手法、および、測地距離の算出における２点間の最短経路を探索する手法の詳細は、例えば非特許文献３のＩＳＯＭＡＰ、非特許文献４のダイクストラ法などが広く知られているため、ここでは処理手順の詳細説明を省略する。
（非特許文献３）Ｊｏｓｈｕａ　Ｔｅｎｅｎｂａｕｍ，Ｖｉｎ　ｄｅ　Ｓｉｌｖａ，Ｊｏｈｎ　Ｌａｎｇｆｏｒｄ，“Ａ　Ｇｌｏｂａｌ　Ｇｅｏｍｅｔｒｉｃ　Ｆｒａｍｅｗｏｒｋ　ｆｏｒ　Ｎｏｎｌｉｎｅａｒ　Ｄｉｍｅｎｓｉｏｎａｌｉｔｙ　Ｒｅｄｕｃｔｉｏｎ”，Ｓｃｉｅｎｃｅ，ＶＯＬ２９０，ｐｐ．２３１９－２３２２，２２　Ｄｅｃｅｍｂｅｒ，２０００
（非特許文献４）Ｅ．Ｗ．Ｄｉｊｋｓｔｒａ，“Ａ　ｎｏｔｅ　ｏｎ　ｔｗｏ　ｐｒｏｂｌｅｍｓ　ｉｎ　ｃｏｎｎｅｘｉｏｎ　ｗｉｔｈ　ｇｒａｐｈｓ”，Ｎｕｍｅｒｉｓｃｈｅ　Ｍａｔｈｅｍａｔｉｋ，ｐｐ．２６９－２７１，１９５９
　さらに、上記式６で算出した、Ｉ個の移動軌跡間の測地距離gk(i,j)から、領域分割候補生成部１０７は、下記式７に示されるＩ×Ｉの測地距離のマトリクスGkを生成する。
Figure JPOXMLDOC01-appb-M000007
　上記した処理によって、測地距離算出ステップＳ２０４では、測地距離算出部１０６は、Ｋ個の閾値Ｒkに対応するＫ個の測地距離マトリクスGkを生成する。
　ここで、上記式５及び上記式６に示した非線形化及び測地距離の算出処理について、図７（ａ）～図７（ｃ）の概念図を用いて説明する。まず、図７（ａ）は、上記式１に示される移動軌跡ｘのデータの分布を、説明の都合上２次元のデータ分布として示したものである。ここで、それぞれのデータ点は、上記式１で示した画素iの移動軌跡に相当する。上記式２で得られる距離f(i,j)の関係を、図７（ｂ）に示す。データ点ｉとデータ点ｊとの距離は、データ点ｉとデータ点ｓとの距離よりも小さくなる。一方、上記式５及び上記式６に示される測地距離変換を行うと図７（ｃ）に示すように、データ点ｉとデータ点ｊとの距離g(i,j)は、データ点を矢印のように中継のデータ点ｓを辿った距離となる。結果として、距離f(i,j)を用いる場合と異なり、データ点ｉとデータ点ｊとの距離g(i,j)は、データ点ｉとデータ点sとの距離g(i,s)よりも大きくなる。
　次に、このような上記式５及び上記式６に示した測地距離変換の特徴を、図８（ａ）及び図８（ｂ）の概念図を用いて説明する。ここでは、線形距離f(i,j)と測地距離gk(i,j)の違いを分かりやすく説明するため、上記式２に示すような時刻ｔにおける移動軌跡間距離を例とする。図８（ａ）は、線形距離f(i,j)の例である。例えば、頭部の画素i５０２と手先部の画素ｊ５０３との距離は、距離５０１に示す距離となる。一方、上記式５及び上記式６に示される測地距離変換を行うことによって、閾値Ｒkが適切に設定されている場合、図８（ｂ）に示されるように、頭部の画素i５０２と手先部の画素ｊ５０３との距離は、画素ｓ５０４を通って画素ｊにたどり着くまでの矢印で示したような距離の和となる。
　そのため、図８（ａ）に示される距離５０１では人物のような関節で繋がった形状をデータとして連続的に表現できないのに対して、図８（ｂ）に示される測地距離では、関節が繋がった形状を距離として連続性を表現することが可能となる。
　また、図８（ａ）の頭部の画素i５０２と手先部の画素ｊ５０３の線形距離は、人物の姿勢の変化に伴って、位置関係が時間的に大きく変化する場合に、その値が時間的に大きく変化する。しかし、同じ２つの移動軌跡間の測地距離gk(i,j)は、類似した動きをする他の移動軌跡との距離の和になるため、線形距離に比べてその変動が小さいという特徴を持つ。
　さらに、図４や図５中の２名の人物のように、大きく異なる動きをする移動体上の２つの移動軌跡については、軌跡間の線形距離はともに大きな値となり、測地距離はさらに大きな値となる。
　以上のことから、人物のように変形しながら移動する移動体を対象とした場合、移動軌跡の距離に基づいて移動体の領域を抽出するためには、線形距離よりも測地距離の方が適していると言える。
　なお、測地距離算出ステップＳ２０４において、線形距離から測地距離を求める手法として、上記式５及び上記式６を用いる手法を示したが、測地距離を求める手法は、この手法に限定されるものではない。
　例えば、あらかじめ定めたＫ個の閾値Ｒkの代わりに、あらかじめ定めたＫ個の閾値Ｎkを用いる。そして、線形距離f(i,j)から非線形化した距離f´k(i,j)を求める処理として、閾値Ｒk以上の線形距離f(i,j)を無限大に置き換える上記式５の代わりに、ある移動軌跡ｉと他の(I-1)個の移動軌跡との線形距離f(i,j)のうちで、小さいほうからＮk番目の線形距離よりも大きい線形距離を無限大で置き換えることによって、非線形化した距離f´k(i,j)を算出してもよい。
　次に、領域分割候補生成ステップＳ２０５では、領域分割候補生成部１０７は、測地距離算出部１０６で算出したＫ個の閾値Ｒkに対応するＫ個の測地距離マトリクスGkに対し、各測地距離マトリクスGk内で連続な移動軌跡間を１つの領域としてまとめることでクラスタリングを行い、クラスタのラベルθとクラスタ数の情報を付与する。ここで２つの移動軌跡が連続とは、移動軌跡iと移動軌跡j間の測地距離gk(i,j)が有限である（無限大ではない）とする。
　Ｋ個の閾値Ｒkに対して得た測地距離を用いたクラスタリングの例を、図９（ａ）～図９（ｅ）を用いて説明する。ここで、図９（ａ）は、２人の人物を移動体としたＴ枚のピクチャを入力として得られたＩ個の移動軌跡の例を示す図である。なお、この図ではａ～ｈまでの８個の移動軌跡を示しているが、本発明は、移動軌跡の個数を限定するものではなく、移動軌跡の個数はできるだけ多くすることが好ましい。図９（ｂ）は、図９（ａ）に示した複数の移動軌跡からなる高次元空間の概念図である。説明を容易にするため３次元空間として示しているが、実際には、移動軌跡間の距離を決定するパラメータの個数に依存するので、３次元になるとは限らない。ここで、移動軌跡からなる高次元空間（図９（ｂ））の１点が、それぞれ上記式１に示した一つの移動軌跡に対応する。さらに、高次元空間（図９（ｂ））上で、点と点との距離は、上記式３の距離f(i,j)に対応する。閾値Ｒkが十分に大きな値である場合、例えば、上記式６においてf(i,j)の最大値よりも閾値Ｒkが大きい場合には、式５に示される非線形化により、図９（ｃ）に示すように測地距離gk(i,j)は、すべてのi,jの組合せにおいて有限の距離となる。すなわち、不連続点が１点もないためクラスタは１個のクラスタθ1 1となる。一方、閾値Ｒkが十分に小さい場合、具体的には、上記式５においてf(i,j)の最小値よりも閾値Ｒkが小さい場合には、上記式５に示される非線形化により、すべてのi,jの組合せにおいてgk(i,j)が無限大となる。すなわち、クラスタ数は移動軌跡の数Ｉと同数となる。したがって、閾値Ｒkをf(i,j)の最大値と最小値の間の値に設定し、複数の測地距離マトリクスを算出すると、測地距離マトリクスから１個以上Ｉ個以下の異なるクラスタ数をもつクラスタリングの情報、すわなち、移動体の領域抽出の候補を得ることができる。
　閾値Ｒkをf(i,j)の最大値と最小値の間の値に設定した場合のクラスタリングについて、図９（ｄ）に示される例について説明する。図９（ｂ）において、移動軌跡ａと移動軌跡ｂとの距離をf(a,b)とした時に、f(d,e) > f(e,g)であるとする。ここでは、閾値をR1として設定した場合に、距離f(d,e)は、閾値Ｒ1よりも大きな値を持つ（つまり、ｆ（ｄ，ｅ）＞Ｒ1）とする。この場合、上記式５に示される非線形化により、上記式６によって測地距離を求めてもg1(d,e)は無限大となる。そこで、領域分割候補生成部１０７は、移動軌跡ｄと移動軌跡ｅとの間を不連続と判定する。この結果、移動軌跡ａ、ｂ、ｃ、ｄ間の測地距離は不連続点を通らないため有限の値を取り、移動軌跡ａ、ｂ、ｃ、ｄから移動軌跡ｅ、ｆ、ｇ、ｈの測地距離は、すべて無限大となる。このように、領域分割候補生成部１０７は、測地距離が有限な複数の移動軌跡の組を同じクラスタとし、無限大となる場合は別のクラスタとする。これによって、図９（ｃ）に示される１つのクラスタθ1 1（ａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈの組）は、図９（ｄ）に示されるようにθ1 2（ｅ、ｆ、ｇ、ｈの組）、θ2 2（ａ、ｂ、ｃ、ｄの組）の２つのクラスタに分離することができる。さらに、図９（ｅ）に示すように、閾値Ｒ2をＲ1>Ｒ2>ｆ(e,g)とした場合に、g1(d,e)は変わらずに（つまり、無限大のまま）、g2(e,g), g2(e,h), g2(f,g), g2(f,h)が無限大になったとする。すると、領域分割候補生成部１０７は、それぞれ移動軌跡ｅと移動軌跡ｇとの間、移動軌跡ｅと移動軌跡ｈとの間、移動軌跡ｆと移動軌跡ｇとの間、及び、移動軌跡ｆと移動軌跡ｈとの間が不連続点であると判定し、図９（ｄ）の場合と同様に測地距離が無限大となる組と無限大にならない組とを整理して、θ1 3（ｇ、ｈの組）、θ2 3（ａ、ｂ、ｃ、ｄの組）、θ3 3（ｅ、ｆの組）の合計３つのクラスタに分離する。以上の処理によって、測地距離が無限大とならない移動軌跡の組は連続とすることで同じクラスタと判定することができ、測地距離が無限大となる移動軌跡の組は不連続とすることによって、不連続点をもとにクラスタを分離することができる。
　なお、閾値Ｒkの設定方法については、f(i,j)の最小値から最大値の間を均等にＫ個設定しても良いし、f(i,j)の平均値やメディアンを中心に一定間隔で増加、減少させた値を用いても良い。
　上記した処理によって、領域分割候補生成ステップＳ２０５では、領域分割候補生成部１０７は、Ｋ個の測地距離マトリクスGkに対応して、連続した移動軌跡であることを示すクラスタのラベルθk mの情報と、クラスタ数Mkを生成する。以降のステップでは、この複数の測地距離マトリクスと対応付けられた各クラスタの情報を、ピクチャ中の移動体の領域を示す複数の候補である領域分割候補として扱う。
　次に、領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、領域分割候補生成ステップＳ２０５で生成された領域分割候補の情報、すわなち、Ｋ個の測地距離マトリクスgk(i,j)とそれに対応するクラスタのラベルθk m、クラスタ数Mkの情報を入力として、複数の領域分割候補に対応する領域間測地距離を算出する。
　以降、領域間測地距離算出ステップＳ２０６での領域間測地距離算出部１０８の動作をさらに詳しく説明する。
　まず、領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、Ｋ個の閾値Ｒkに対応する測地距離マトリクスgk(i,j)から、クラスタ数Ｍ（Ｍは２以上）ごとに任意に１つを選択して、これをクラスタ数Ｍを代表する代表測地距離マトリクスGMとする。本実施の形態１では、代表測地距離マトリクスを選択する方法として、クラスタ数がＭである複数の測地距離マトリクスのうち、閾値Ｒkがもっとも大きいものを選択するものとする。
　次に、領域間測地距離算出部１０８は、クラスタ数Ｍの代表測地距離マトリクスGMに対して、Ｍの次にクラスタ数の少ない複数の測地距離マトリクスから任意に１つを選択し、これをクラスタ数Ｍの参照マトリクスGrMとする。本実施の形態１では、参照マトリクスを選択する方法として、Ｍの次にクラスタ数の少ない複数の測地距離マトリクスのうち、閾値Ｒkがもっとも小さいものを選択するものとする。
　図１０（ａ）～図１０（ｆ）に、領域間測地距離算出ステップＳ２０６で生成した、測地距離マトリクスGkと、代表測地距離マトリクスGMの例を示す。図１０（ａ）はＫ個の閾値Ｒkに対して得た測地距離マトリクスGkの例を示す図である。測地距離マトリクスは、移動軌跡の測地距離gk(i,j)をi行j列の要素とする、Ｉ×Ｉの測地距離の行列である。図１０（ｂ）～図１０（ｄ）は、それぞれ、クラスタ数１～３の代表測地距離マトリクスGMの例を示す図である。ここでは図１０（ｂ）～図１０（ｄ）の代表測地距離マトリクスの行、列に対応する移動軌跡は、すべて共通であるものとする。
　図１０（ｂ）と図９（ｃ）、図１０（ｃ）と図９（ｄ）、図１０（ｄ）と図９（ｅ）は、それぞれクラスタ数が１～３の場合の代表測地距離マトリクス、及び、移動軌跡の距離の高次元空間の概念図である。
　図１０（ｂ）～図１０（ｄ）の矩形の斜線部は、有限の値をもち、これは対応する移動軌跡が連続であり、１つのクラスタを構成することを表している。また、図中の斜線部以外の領域は、距離は無限大となり、対応する移動軌跡が不連続であることを表している。したがって、クラスタ数Ｍに応じて、対角部にＭ個の有限距離のクラスタ（Ｍ個の斜線部）が並ぶ配置となっている。
　図１０（ｅ）及び図１０（ｆ）は、参照マトリクスの例を示す図である。クラスタ数Ｍの参照マトリクスは、クラスタ数がＭ未満のうち最大のクラスタ数となる測地距離マトリクスから選ばれる。そのため、代表測地距離マトリクスにおいて無限大となる要素が、参照マトリクスにおいては有限の値となる箇所がある。
　以降、あるクラスタ数がＭの代表測地距離マトリクスと参照マトリクスが含む情報について、図１１（ａ）～図１１（ｄ）を用いて詳しく説明する。
　図１１（ａ）及び図１１（ｂ）は、それぞれ、クラスタ数２（Ｍ=２）の場合の代表測地距離マトリクス（図１１（ａ））と参照マトリクス（図１１（ｂ））の例を示す図である。代表測地距離マトリクスのクラスタθ1 2、θ2 2に対応する、参照マトリクスのクラスタを同様にθ1 2、θ2 2とする（図１１（ｂ）に示される２つの斜線領域）。また、代表測地距離マトリクスにおいては値が無限大であり、かつ参照マトリクスにおいては値が有限となる要素の領域（図１１（ｂ）中の２つの縦線領域）をθ1,2 2とする。
　このとき、参照マトリクスのθ1 2領域はクラスタθ1 2内の移動軌跡間の距離を、θ2 2領域はクラスタθ2 2内の移動軌跡間の距離を、それぞれ表す。また、参照マトリクスの２つのθ1,2 2の領域は、異なるクラスタθ1 2、θ2 2に存在する移動軌跡間の距離を表す。このことから、参照マトリクスのθ1 2内の距離の平均値によってクラスタθ1 2の分布のばらつき度合いを、参照マトリクスのθ2 2内の距離の平均値によってクラスタθ2 2の分布のばらつき度合いを、それぞれ表すことができると言える。さらに、参照マトリクスのθ1,2 2内の距離の平均値によってクラスタθ1 2とθ2 2間の距離を表すことができる。
　クラスタ数が２以外の場合でも同様である。例えば、クラスタ数３（Ｍ=３）の場合の代表測地距離マトリクス（図１１（ｃ））と参照マトリクス（図１１（ｄ））の例においても、代表測地距離マトリクスのクラスタθ1 3、θ3 3と参照マトリクスθ1,3 3の間で、上記と同じ関係が成り立つ。
　以上のような代表測地距離マトリクスと参照マトリクスが含む情報を利用し、領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、クラスタ間の距離の指標である領域間測地距離を算出する。
　具体的には、クラスタ数Ｍの代表測地距離マトリクスGMと参照マトリクスGrMから、代表測地距離マトリクスGMでは無限大であり、かつ、参照マトリクスGrMでは有限となる要素に対応する領域θp,q M、および、クラスタθp M、θq Mを抽出する。
　そして、領域間測地距離算出部１０８は、クラスタθp M、θq M間の領域間測地距離hp,q Mを下記式８により算出する。
Figure JPOXMLDOC01-appb-M000008
　上記式８において、g_M pは、２つの領域分割候補に対応する２つのクラスタθp M、θq Mのうち、クラスタθp M内の複数の移動軌跡間の測地距離の平均値である。同様に、g_M qは、クラスタθq M内の複数の移動軌跡間の測地距離の平均値である。g_M p,qは、クラスタθp Mに存在する移動軌跡とクラスタθq Mに存在する移動軌跡との間の測地距離の平均値である。ｎpおよびｎqは、クラスタθp Mおよびθq Mに属する移動軌跡の個数である。
　なお、g_M p、g_M q、g_M p,qは、いずれも参照マトリクスGrMを用いて計算してもよいし、g_M pおよびg_M qは、代表測地距離マトリクスGMを、g_M p,qは参照マトリクスGrMをそれぞれ用いて計算しても良い。
　領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、上記した処理を、クラスタ数Ｍのうち１を除く、算出された全てのクラスタ数に対して行い、それぞれ領域間測地距離hp,q Mを算出し、対応するクラスタθp M、θq M（移動軌跡のラベル情報）を領域分割候補としてあわせて出力する。
　なお、ある１つのクラスタ数Ｍの代表測地距離マトリクスGMと参照マトリクスGrMに対し、上記したθp,q M、θp M、θq Mの領域が１組とは限らない。２組以上ある場合においても、上記式８に示される処理により、領域間測地距離を算出する。
　ここで、上記式８に示される領域間測地距離の性質について説明する。上記式８から、領域間測地距離は、異なる２つの領域分割候補に属する移動軌跡間の測地距離の平均値であるg_M p,qを、同一領域分割候補内の移動軌跡間の測地距離の平均値であるg_M p、g_M qで正規化した値となっている。言い換えると、領域間測地距離は、領域分割候補間の距離を表す指標を領域分割候補内のばらつきを表す指標で正規化した値となっている。そのため、領域間測地距離は、定性的には以下の性質を持つ。
・２つの領域分割候補の間の距離が大きくなるほど、領域間測地距離も大きくなる。
・移動軌跡全体の大きさ（拡縮率）が変化する場合は、領域間測地距離は一定になる。
・移動体の変形によって、領域分割候補内の移動軌跡間の距離が変動しても、領域間測地距離はあまり変わらない。
　このように、領域間測地距離算出部１０８は、複数の閾値のそれぞれに対して領域分割候補生成ステップＳ２０５で生成された複数の領域分割候補のセットのうちの第１の領域分割候補のセットにおける２つの領域分割候補間の類似度として、当該２つの領域分割候補における測地距離である代表測地距離と、当該第１の領域分割候補のセットに含まれる領域分割候補の総数よりも次に小さい総数だけ領域分割候補が含まれる第２の領域分割候補のセットにおける測地距離である参照測地距離とを用いて、予め定められた演算をすることで、領域間測地距離を算出する。つまり、参照測地距離マトリクスに含まれる領域分割候補間の測地距離を、代表測地距離マトリクスに含まれる領域分割候補の各領域内の測地距離で正規化する。言い換えると、参照測地距離と代表測地距離に基づいて、２つの領域分割候補間の距離を表す指標と、各領域分割候補内のばらつきを表す指標とを算出し、その距離を表す指標を、そのばらつきを表す指標で正規化する演算をすることで、領域間測地距離を算出する。
　なお、領域分割候補生成ステップＳ２０５で生成される複数の領域分割候補のうち、少なくとも１つの領域分割候補は１個の移動軌跡が属するものであってもよい。このとき、領域間測地距離算出ステップＳ２０６では、１個の移動軌跡が属する領域分割候補と他の領域分割候補との領域間測地距離として、その１個の移動軌跡と他の領域分割候補に属する任意の１つの移動軌跡との測地距離を出力すればよい。
　次に、領域分割候補選択ステップＳ２０７では、領域分割候補選択部１０９は、領域分割候補生成部１０７で生成された複数のクラスタθp M、θq Mを領域分割候補とし、その評価値として、領域間測地距離算出部１０８で算出された領域間測地距離hp,q Mを扱い、領域間測地距離に基づいてクラスタθp M、θq Mの領域分割候補を別個のクラスタとして分割するか否かを選択する。
　具体的には、領域間測地距離hp,q Mが、あらかじめ定められた閾値Htより大きい場合、対応する２つのクラスタθp M、θq Mは、その領域間の距離が十分離れているクラスタとして選択し、個別のクラスタとして確定する。一方、領域間測地距離hp,q Mが、あらかじめ定められた閾値Htより小さい場合、対応する２つのクラスタθp M、θq Mは、同一のクラスタとして確定する。つまり、この場合には、分割しないと確定する。そして、領域分割候補の全てのクラスタに対して、分割するか否かを判定した後、異なるクラスタに属する移動軌跡には異なるラベルθmを割り当て、移動軌跡のクラスタリング情報として出力する。
　例えば、図１１（ａ）に示されるクラスタ数２の代表測地距離マトリクスと、図１１（ｂ）に示される参照マトリクスから算出された領域間測地距離をh1,2 2とし、図１１（ｃ）に示されるクラスタ数３の代表測地距離マトリクス、図１１（ｄ）に示される参照マトリクスから算出された領域間測地距離をh1,3 3、他のクラスタ数wの領域間測地距離をhp,q wとする。ここで、h1,2 2>Htで、かつ、h1,3 3、 hp,q w<Htであるとすると、対応するクラスタθ1 2、θ2 2は、このように分割され、他のクラスタは分割されない（つまり、θ1 2がさらにθ1 3、θ3 3に分割されることはない）。その結果、移動軌跡はクラスタθ1 2、θ2 2の２つのクラスタに分割され、図９（ｄ）と同様なクラスタリング結果を得る。
　最後に、画像出力ステップＳ２０８において、出力部１０５は、移動軌跡のクラスタθ1 2、θ2 2から、画像を生成して、ディスプレイ１２０に表示する。
　ここで、画像出力ステップＳ２０８では、出力部１０５は、I個の移動軌跡に対し、対応するクラスタθ1 2、θ2 2によって異なる色を選択し、選択した色でそれぞれＴ番目の画像座標位置の画素を描画することで、画像を生成する。
　図１２に画像出力ステップＳ２０８で生成した画像の例を示す。クラスタリングした移動軌跡ごとに異なる色を持つ画像が表示されることとなる。
　なお、画像出力ステップＳ２０８において、クラスタリングしたI個の移動軌跡に基づいて画像を生成する手順として、I個の移動軌跡の画像座標位置の画素をクラスタに応じた色で描画するとしたが、画像を生成する方法をこれに限定するものではない。
　具体的には、移動軌跡の数Ｉと画像全体の画素数とが同数であれば、上述した方法により画像中の全画素をクラスタに応じた色で描画することができる。一方、移動軌跡の数Ｉが画像全体の画素数より少ない場合、どの移動軌跡の画像座標位置とも一致しない画素が存在する。このような移動軌跡の画像座標位置と一致しない画素については、別の方法で描画しても良い。
　例えば、動き解析部１０２において、ある移動軌跡を生成するための動き検出に用いたブロックに属する画素は、その移動軌跡のクラスタと同じ色で描画するとしても良い。
　また、移動軌跡の画像座標位置と一致しない画素を描画する別の方法として、最近傍の移動軌跡のクラスタと同じ色で描画するとしても良い。
　また、移動軌跡の画像座標位置と一致しない画素を描画する別の方法として、複数の移動軌跡の画像座標位置（点）の間を、Ｄｅｌａｕｎａｙ三角メッシュ生成法にて結び、同一のクラスタに属する３点に囲まれる３角形に含まれる画素は、そのクラスタと同じ色で描画するとしても良い。
　なお、連続した動画像に対して処理を行う場合は、上述したステップＳ２０１～Ｓ２０８の動作を繰り返し行うことで、入力された画像の中から、異なる動きをする領域ごとに移動体の領域を分割抽出する。
　以上のように、本実施の形態の移動体検出装置は、移動軌跡間の距離、すなわち類似度にもとづいて移動軌跡のクラスタリングを行う。そしてクラスタリングの手法として、移動軌跡間の距離に対し、異なる閾値Ｒを用いて測地距離変換し、その結果得られる領域分割の候補を得る。さらに、領域分割の候補に対し、領域間測地距離という新たな指標を導入し、この指標に基づいて分割するか否かを決定する。
　ここで前述したように、領域間測地距離は、移動軌跡全体の大きさ（拡縮率）が変化しても、領域間測地距離は一定になるという効果がある。したがって、ピクチャ上の移動体の大きさが変化するような場合（例えば、カメラの撮影において、ズーミングしたり、移動体が接近してきた場合）であっても、大きさの変化に影響を受けにくく、結果として、大きさが変化するような移動体を含む場合であっても、正しく移動体の領域抽出を行うことが期待できる。
　以上のようにして、本実施の形態における移動体検出装置及び方法によれば、画像の移動軌跡の類似度にもとづいてクラスタリングを行うことによって、画像中を移動する物体の領域を時間的に追跡した結果として、関節物体の姿勢によらずに、画像中の移動体の領域抽出をすることができる。また、前処理として人物候補領域を設定する必要がないため、人物候補領域の検出ミスに起因する領域抽出の失敗がない。以上のように、膨大なパラメータのフィッティングを必要とせずに、領域間測地距離に基づいてクラスタリングを行うことによって安定に、形状が変化しながら移動する人物等を含む画像を領域抽出し、これによって画像中の移動体の検出を行うことが可能となる。
　なお、本発明に係る移動体検出装置及び方法は、上記実施の形態に限定されるものではなく、上記実施の形態に対して当業者が思いつく変形を施して得られる形態や、後述する各種変形例を含む複数の形態における構成要素を任意に組み合わせて得られる形態も本発明に含まれる。
　（実施の形態１の変形例１）
　たとえば、本実施の形態１の移動体検出装置の領域分割候補選択ステップＳ２０７において、閾値Htはあらかじめ定められているものとしたが、これに限定するものではない。具体的には、領域抽出したい移動体の動きの大きさに応じて閾値Htを変化させても良いし、人であるのか車であるのかに応じて閾値Htを変更しても良い。
　閾値Htは、ある２つの領域分割候補に対して、異なる領域とするか同じ領域とするかの評価基準に相当する。例えば、２つの領域分割候補が２つの移動体にそれぞれ対応する場合、閾値Htを小さくすることで、２つの移動体の相対的な位置や動きの違いが小さい場合においても、異なる２つの領域として抽出することができる。逆に、閾値Htを大きくすることで、この２つの移動体の相対的な位置や動きが大きい場合にのみ、２つの領域として抽出することができることとなる。すわなち、閾値Htの大小によって、領域抽出する対象を変えることができるという効果がある。
　（実施の形態１の変形例２）
　なお、本実施の形態１の移動体検出装置の領域分割候補生成ステップＳ２０５、領域間測地距離算出ステップＳ２０６、領域分割候補選択ステップＳ２０７の動作として、あらかじめ定められたＫ個の閾値Ｒkに対応する領域分割候補を生成したうえで、このＫ個の領域分割候補から領域間測地距離に基づいて選択するものとして説明した。しかし、本発明の動作はこれに限定されるものではなく、領域分割候補に対応する領域間測地距離を算出し、これに基づいて領域分割候補を選択する動作であれば、どのような手順であっても良い。
　例えば、閾値Ｒを徐々に小さくしながら領域分割候補の生成、領域間測地距離の算出、領域分割候補の選択を繰り返し行い、ある条件に達した時点で終了する、という手順をとっても良い。
　このような本実施の形態の移動体検出装置における、別の動作の例を、図１３を用いて説明する。
　領域分割候補生成ステップＳ１１０４では、領域分割候補生成部１０７は、まず、移動軌跡間の距離の集まりである距離マトリクスＦを入力して、移動軌跡の近傍を定義する距離の閾値Ｒ0を初期値として、前記移動軌跡間の距離を測地距離に変換し、測地距離マトリクスG0を生成する。ここでは閾値Ｒ0は、距離マトリクスＦの要素の最大値とする。このときクラスタ数はＭ=1となる。次に、閾値Ｒ0をある一定の率で減少させたRiを用いて、測地距離マトリクスGiを生成し、クラスタ数が１より大きくなる（例えばＭ＝２）まで繰り返す。
　領域間測地距離算出ステップＳ１１０５では、領域間測地距離算出部１０８は、領域間測地距離算出ステップＳ２０６と同様に、領域分割候補生成ステップＳ１１０４で生成された測地距離マトリクスを用いて、クラスタ数Ｍ（Ｍ＝２）の代表測地距離マトリクスGMと参照マトリクスGrMを選択して、クラスタ数Ｍ（Ｍ＝２）の領域間測地距離を算出する。
　領域分割候補選択ステップＳ１１０６では、領域分割候補選択部１０９は、領域間測地距離があらかじめ定められた閾値Htと比較し、領域間測地距離が大きい場合に領域分割候補を別個のクラスタとして分割するか否かを選択する（Ｓ１１０４～Ｓ１１０６）。
　具体的には、領域分割候補選択ステップＳ１１０６では、領域分割候補選択部１０９は、領域間測地距離が閾値Htより大きい場合は、上述の領域分割候補生成ステップＳ１１０４から領域分割候補選択ステップＳ１１０６の処理を、閾値Ｒkをさらに小さくしながら繰り返す。一方、領域間測地距離が閾値Htより小さい場合は、繰り返し処理を終了し、繰り返し処理によって選択された領域分割候補に基づいて、移動軌跡をクラスタリングし（Ｓ１１０７）、出力する。
　以上のような領域分割ステップＳ１１０８での動作によっても、上記実施の形態における領域分割ステップＳ２０９と同様に、領域分割の候補に対し、領域間測地距離に基づいて分割するか否かを決定することができる。この領域間測地距離は、移動軌跡全体の大きさ（拡縮率）が変化しても、領域間測地距離は一定になるという効果がある。したがって、画像上の移動体の大きさが変化するような場合であっても、大きさの変化に影響を受けにくく、結果として、大きさが変化するような移動体を含む場合であっても、正しく移動体の領域抽出を行うことが期待できる。
　（実施の形態１の変形例３）
　また、上記実施の形態１では、領域分割候補選択ステップＳ２０７において、領域間測地距離の大きさで、対応する２つの領域分割候補を別個のクラスタとするか否かを判断したが、本発明の領域分割候補の選択基準としては、このような判断基準だけに限るものではなく、例えば、領域間測地距離の時間変化で判断してもよい。
　つまり、いま、上記ステップＳ２０１～Ｓ２０８が、新たな動画像について、繰り返し実行されるとする。このとき、領域分割候補選択ステップＳ２０７では、領域分割候補選択部１０９は、複数のクラスタθp M、θq Mを領域分割候補とし、その評価値として領域間測地距離の時間変化、すなわち新たに入力した領域間測地距離hp,q Mと、前回の処理で算出された対応するクラスタに対する領域間測地距離hp,q Mとの差分を算出し、あらかじめ定められた閾値Htより大きい場合に、クラスタθp M、θq Mの領域分割候補を別個のクラスタとして分割してもよい。
　具体的には、領域分割候補選択ステップＳ２０７では、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化に基づいて、領域分割候補を選択し、領域分割の結果として出力してもよい。このとき、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化が、予め定められた閾値より大きい２つの領域分割候補を、異なる領域として選択し、領域分割結果として出力してもよいし、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化が、予め定められた閾値より小さい２つの領域分割候補を、同一の領域として選択し、領域分割結果として出力してもよい。また、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化に基づいて、（１）大きいほど２つの領域分割候補は異なる領域となるように、かつ、（２）小さいほど２つの領域分割候補を同一の領域となるように領域分割候補を選択し、領域分割結果として出力してもよい。
　また、距離算出ステップ及び領域分割ステップは、新たな動画像について、繰り返し実行され、領域分割候補選択ステップＳ２０７では、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、繰り返し実行において領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化が予め定められた閾値よりも大きい２つの領域分割候補の全てを、領域分割の結果として選択し、出力してもよい。
　領域間測地距離の時間変化は、クラスタ間の距離の時間変化に比例する。そのためこの値が大きいほど、対応する２つのクラスタは巨視的に異なる動きをしていると言える。したがって、領域間測地距離の時間変化に基づいて領域分割候補を選択することで、異なる動きをする移動体領域を別のクラスタとして正しく領域抽出できることが期待できる。
　さらに、図８を用いて説明したように、移動軌跡間の測地距離は、以下の特徴を持つ。
・人物のように多関節状の変形を伴う移動体上の２つの移動軌跡において、移動軌跡間の測地距離の時間変化が小さい。
　このことから、領域分割候補間の領域観測地距離についても、同様に以下の特徴を持つ。
・多関節状の変形を伴う移動体上の２つの領域分割候補において、領域分割候補間の領域間測地距離の時間変化が小さい。
　以上のことから、領域分割候補選択ステップＳ２０７およびＳ１３０７において、移動軌跡間の測地距離の時間変化、または、領域間分割候補の領域間測地距離の時間変化を用いて、領域分割候補の選択を行うことで、正しく移動体を検出することができるという効果を得ることができる。
　（実施の形態２）
　上記した本実施の形態１では、領域分割候補生成部１０７は、測地距離算出部１０６で算出した移動軌跡間の測地距離に基づいて領域分割候補を複数生成するとしたが、領域分割候補を生成する方法をこの方法に限定するものではなく、移動軌跡の集まりである領域分割候補を複数生成する手法であれば、他の方法であっても良い。
　以下、本発明の実施の形態２では、領域分割候補を生成する他の方法の一例として、移動軌跡に対応する複数のピクチャの画素の輝度値に基づいて、領域分割候補を複数生成する方法について図面を用いて説明する。
　実施の形態２における移動体検出装置１００の構成は図１と同じである。本実施の形態２において、実施の形態１と異なる点は、領域分割部１０４の動作である。
　以下、本実施の形態２の移動体検出装置１００の動作を、図１４を用いて説明する。
　図１４は、本実施の形態２の移動体検出装置１００の動作を表すフローチャートである。図１４において、７つのステップＳ２０１～Ｓ２０３、Ｓ２０８、Ｓ２０９、およびＳ１３０４～Ｓ１３０７は、それぞれ図１の各処理部に対応している。すわなち、画像入力部１０１では画像入力ステップＳ２０１、動き解析部１０２では動き解析ステップＳ２０２、距離算出部１０３では距離算出ステップＳ２０３、測地距離算出部１０６では測地距離算出ステップＳ１３０４、領域分割候補生成部１０７では領域分割候補生成ステップＳ１３０５、領域間測地距離算出部１０８では領域間測地距離算出ステップＳ１３０６、領域分割候補選択部１０９では領域分割候補選択ステップＳ１３０７、出力部１０５では画像出力ステップＳ２０８の各動作を実行する。領域分割部１０４は、領域分割ステップＳ２０９に対応する。
　本実施の形態２において、画像入力ステップＳ２０１～距離算出ステップＳ２０３までの動作は、実施の形態１と同じである。
　画像入力ステップＳ２０１において、画像入力部１０１は、カメラ１１０から、動画像を構成する複数のピクチャを取得する。ここではＴ枚のピクチャを取得するものとする。
　次に、動き解析ステップＳ２０２において、動き解析部１０２は、入力された複数のピクチャ間の動き情報を算出し、複数の移動軌跡を生成して出力する。ここではＩ個の移動軌跡が生成するものとする。
　そして、距離算出ステップＳ２０３において、距離算出部１０３は、I個の移動軌跡を入力として移動軌跡間の線形距離を算出する。
　上記の画像入力ステップＳ２０１～距離算出ステップＳ２０３までの動作により、図４における撮影状況において、撮影されたＴ枚のピクチャが図５であり、Ｔ枚のピクチャから得られる移動軌跡の例が図６であるとする。また、画像入力ステップＳ２０１～距離算出ステップＳ２０３により、Ｔ枚のピクチャにわたるＩ個の移動軌跡間の距離f(i,j)を算出して、Ｉ×Ｉの距離マトリクスＦとして出力する。
　以下、本実施の形態２における、領域分割部１０４の動作を説明する。
　測地距離算出ステップＳ１３０４において、測地距離算出部１０６は、距離算出ステップＳ２０３で算出したＩ個の移動軌跡間の線形距離f(i,j)に対して、あらかじめ定められた閾値Ｒを用いて、上記式５および上記式６により、測地距離g(i,j)を算出する。そして、Ｉ個の移動軌跡間の測地距離g(i,j)であるＩ×Ｉの測地距離のマトリクスGを出力する。
　次に、領域分割候補生成ステップＳ１３０５において、領域分割候補生成部は１０７、画像入力部で取得したＴ枚のピクチャに基づいて、ピクチャ上の小領域を複数生成し、生成したピクチャ上の複数の小領域にそれぞれ対応する移動軌跡の集まりである領域分割候補を生成する。
　以下、領域分割候補生成部１０７において、Ｔ枚のピクチャに基づいて、領域分割候補を生成する手順について詳しく説明する。
　本実施の形態２では、領域分割候補生成部１０７は、画像入力部で取得したＴ枚のピクチャから、時間順の中央となるＴ／２番目のピクチャを１枚選択する。次に、領域分割候補生成部１０７は、選択した１枚のピクチャに対して、ピクチャの複数の画素の色類似度に基づいて、ピクチャを複数の小領域に分割する。ここではＫ個の小領域に分割されたものとする。
　画素の色類似度に基づいて、ピクチャを複数の小領域に分割する手法は、例えば、非特許文献５に記載されている手法などを用いることができるため、ここでは詳細の説明を省略する。
　（非特許文献５）Ｐｅｄｒｏ　Ｆ．　Ｆｅｌｚｅｎｓｚｗａｌｂ　ａｎｄ　Ｄａｎｉｅｌ　Ｐ．　Ｈｕｔｔｅｎｌｏｃｈｅｒ　“Ｅｆｆｉｃｉｅｎｔ　Ｇｒａｐｈ－Ｂａｓｅｄ　Ｉｍａｇｅ　Ｓｅｇｍｅｎｔａｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ，Ｖｏｌ．５９，Ｎｏ．２，ｐｐ．１６７－１８１，Ｓｅｐｔ，２００４
　さらに、領域分割候補生成部１０７は、Ｋ個の小領域に対応する移動軌跡の集まりを領域分割候補として出力する。具体的には、選択したピクチャのＫ個の小領域を表すＫ種類のラベルをθkとする。それぞれの移動軌跡に含まれる、選択したピクチャ上の画素座標から、その画素座標を含む小領域を特定し、特定した小領域のラベルθkを移動軌跡に対応付ける。このようにして得られた、Ｉ個の移動軌跡にそれぞれ対応付けられたＫ種類のラベルθkによって、各移動軌跡が属するＫ個の領域分割候補を表す。
　図１５（ａ）～図１５（ｄ）に、領域分割候補生成部１０７によって生成された、領域分割候補の例の図を示す。図１５（ａ）は、動き解析部１０２で算出されるＴ枚のピクチャにわたる複数の移動軌跡ａ～ｈの例である。図１５（ｂ）はＴ枚のピクチャから選択したＴ／２フレーム目のピクチャの例の図である。そして、図１５（ｃ）は、選択したピクチャの画素の色類似度に基づいて、複数の小領域に分割した結果の例を示す。ここでは、２名の人物がそれぞれ２つの領域に分割され、あわせて４個の小領域に分割されたものとする。図１５（ｄ）は、移動軌跡ａ～ｈを図１５（ｃ）の小領域に対応づけることで生成された領域分割候補の例を示す。図１５（ｄ）における領域分割候補のラベルθ1～θ4は、図１５（ｃ）の４つの小領域に対応している。８つの移動軌跡ａ～ｈに対応付けられたラベルθ1～θ4によって、それぞれの移動軌跡が属する領域分割候補を表している。領域分割候補生成部１０７は、このようにして生成した複数の領域分割候補を出力する。
　なお、上記した画素の色類似度に基づいてピクチャを複数の小領域に分割する手法では、一般的に分割の粒度を設定する可変パラメータが存在する。本実施の形態２においては、好適には、生成される小領域が、それぞれ同一の移動体上の一部となるように、可変パラメータを設定する。言い換えると、生成される１つの小領域が２つ以上の移動体上に存在することが無いように可変パラメータを設定する。
　なお、図１５（ｃ）の小領域の分割結果において、実際には人物以外の背景領域も個別の小領域として抽出されることとなるが、ここでは図面を用いた説明の都合上、背景領域については省略する。
　次に、領域間測地距離算出ステップＳ１３０６では、領域間測地距離算出部１０８は、領域分割候補生成ステップＳ１３０５で生成された領域分割候補の情報、すわなち、Ｉ個の移動軌跡間の測地距離g(i,j)と、Ｉ個の移動軌跡に対応する領域分割候補のラベルθkを入力として、Ｋ個の領域分割候補間の領域間測地距離を算出する。
　本実施の形態２では、２つの領域分割候補θpと領域分割候補θqの間の領域間測地距離hp,qを、以下の式９によって算出する。
Figure JPOXMLDOC01-appb-M000009
　上記式９において、g_ p,qは、領域分割候補θpに属する移動軌跡と、領域分割候補θqに属する移動軌跡との間の測地距離の平均値である。g_ pおよびg_ qは、それぞれ、領域分割候補θpに属する複数の移動軌跡間の測地距離の平均値、および、領域分割候補θqに属する複数の移動軌跡間の測地距離の平均値である。ｎpおよびｎqは、領域分割候補θpおよびθqに属する移動軌跡の個数である。
　領域間測地距離算出部１０８は、Ｋ個の領域分割候補間の全ての組み合わせにおいて、領域間測地距離を算出する。
　次に、領域分割候補選択ステップＳ１３０７では、領域分割候補選択部１０９は、領域分割候補生成部１０７で生成されたＫ個の領域分割候補、および、領域間測地距離算出部１０８で算出された領域間測地距離に基づいて、複数の領域分割候補の間で分離または結合を選択することによって、移動軌跡をクラスタリングする。
　具体的には、ある２つの領域分割候補θpおよびθqについて、その領域間測地距離hp,qが、あらかじめ定められた閾値Htより小さい場合、領域分割候補選択部１０９は、２つの領域分割候補を結合する処理を行う。２つの領域分割候補を結合する場合、領域分割候補選択部１０９は、いずれか一方の領域分割候補に属する移動軌跡のラベル（例えばθq）を、他方の領域分割候補のラベル（例えばθp）で置き換える。
　領域分割候補選択部１０９は、上述したある２つの領域分割候補間の結合を判定する処理を、全ての領域分割候補間の組み合わせに対して行う。その結果得られる移動軌跡に対応付けられたラベルによって、それぞれの移動軌跡が属する領域、すなわち移動軌跡をクラスタリングした結果を表す。
　例えば、図１５（ｄ）に示される４つの領域分割候補間の領域間測地距離のうち、領域分割候補θ1とθ2間の領域間測地距離h1,2、および、領域分割候補θ3とθ4間の領域間測地距離h3,4の２つについて、閾値Htより小さく（h1,2＜Ht、h3,4＜Ht）、他の領域分割候補間の領域間測地距離は閾値Htより大きいとする。このとき、上述した領域分割候補選択部１０９の動作によって、領域分割候補θ2に属する移動軌跡ｃ、ｄのラベルθ2はθ1に置き換えられ、領域分割候補θ4に属する移動軌跡ｇ、ｈのラベルθ4はθ3に置き換えられる。その結果、複数の移動軌跡（図１６（ａ）参照）は、２つの領域θ1とθ3にクラスタリングされる（図１６（ｂ）参照）。
　最後に、画像出力ステップＳ２０８において、出力部１０５は、本実施の形態１と同様に、移動軌跡のクラスタθ1，θ3から、画像を生成して、ディスプレイ１２０に表示する。
　図１６(ｃ)および図１６（ｄ）に、出力部１０５で生成した１フレーム目およびＴフレーム目の画像の例を示す。クラスタリングした移動軌跡ごとに異なる色を持つ画像が表示されることとなる。
　以上のように、本実施の形態２の移動体検出装置は、移動軌跡の集まりである領域分割候補を生成し、領域分割候補間で算出される領域間測地距離に基づいて移動軌跡のクラスタリングを行う。
　この領域間測地距離は、次のような特徴を持つ。
・２つの領域分割候補が全く異なる動きをする場合、領域間測地距離の値が大きく、かつ、時間的な変動も大きい。
・２つの領域分割候補が、変形しながら移動する同一移動体上に存在する場合、領域間測地距離の値は比較的小さく、かつ、時間的な変動が小さい（理想的には一定）。
　そのため、動画像中に、人物のような姿勢および位置の変化によって、画像上の形状や大きさが変化するような移動体が含まれる場合に、ある２つの領域分割候補について、異なる移動体上の領域か、同じ移動体上の領域なのかの判断が容易になる。その結果、正しく移動体の領域抽出を行うことができる。
　上記した領域間測地距離の特徴について、別の実験結果をもとに説明する。図１７（ａ）は、関節状の変形を伴いながら移動する１つの移動体の動画像の例である。図１７（ｂ）は、図１７（ａ）の動画像を入力として、移動体を上下に２分割された領域分割候補に対して算出される、領域間測地距離の実験結果の例である。実験では、図１７（ａ）の３１フレームのピクチャに対し、１～７フレーム、７～１３フレーム、・・・、２５～３１フレームのように、重複した７フレームごとに本発明の実施の形態２と同じ処理を行った。
　図１７（ｂ）から、図１７（ａ）のように領域分割候補が近接して移動する場合、移動軌跡間の線形距離および測地距離は、ともにその値が比較的小さくなる。ここで、領域間測地距離（実線）は、平均ユークリッド距離に対して、時間的な変動が一定であることが分かる。そのため、時間的な変動が一定である、という指標に基づいて領域分割候補の選択を行うことで、ある２つの領域分割候補について、異なる移動体上の領域か、同じ移動体上の領域なのかの判断が容易になる。その結果、正しく移動体の領域抽出を行うことができる。
　（実施の形態１および実施の形態２の変形例４）
　なお、本発明の実施の形態１および実施の形態２では、領域間測地距離は、上記式８および上記式９によって算出するものとしたが、この式に限定するものではない。領域間測地距離は、上記式８および上記式９と同様、２つの領域分割候補間の距離（類似度）を表す指標、および、それぞれの領域分割候補内の移動軌跡のばらつきを表す指標を算出し、距離を表す指標（前者）をばらつきを表す指標（後者）で正規化した指標であればよい。
　具体的には、上記式９における２つの領域分割候補間の距離（類似度）を表す指標であるg_ p,qとして、例えば、下記式１０の移動軌跡間の測地距離の中央値を用いても良い。
Figure JPOXMLDOC01-appb-M000010
　上記式１０において、median{g(i,j)}は、複数の移動軌跡間の測地距離g(i,j)の中央値である。
　また、上記式９における領域分割候補内の移動軌跡のばらつきを表す指標であるg_ pおよびg_ qとして、移動軌跡間の測地距離の分散を用いても良い。
　（実施の形態１および実施の形態２の変形例５）
　本発明の実施の形態１および実施の形態２では、領域分割の結果はディスプレイに表示されたが、領域分割の結果の利用方法としては、このような応用に限られず、例えば、移動体の動き予測に応用してもよい。具体的には、本発明に係る移動体検出装置は、上記実施の形態における構成要素に加え、動き予測部を備えてもよい。つまり、領域分割部１０４で得られた領域分割の結果に基づいて、各領域に含まれる画素の移動軌跡から代表軌跡を算出し、その代表軌跡をもとに移動体の動きを予測する動き予測部を備えてもよい。より詳しくは、本発明に係る移動体検出装置は、領域分割部１０４で特定された領域を構成する移動軌跡から、当該領域を代表する移動軌跡を算出し、算出した代表の移動軌跡に従って当該領域が移動すると予測することで、移動体の動きを予測する動き予測部を備えてもよい。
　具体的には、領域θmに属する画素の移動軌跡をxCmと表現すると、その動き予測部は、まず、下記式１１のように、クラスタ領域θmごとに代表の移動軌跡を求める。なお、下記式１１では、代表の移動軌跡として、平均移動軌跡を算出しているが、その計算に対して画素の移動軌跡xCmごとに重み付け等を行ってもよいし、画像上でのクラスタの重心に対応する画素の移動軌跡を代表の移動軌跡としてもよい。
Figure JPOXMLDOC01-appb-M000011
　ここで、Cmは、領域θmに属する画素数もしくは画素の移動軌跡の数である。
　図１８に、上記式１１に基づいてクラスタ領域θmごとに代表の移動軌跡を求める例を示す。ただし、見やすさを考慮して、頭部に対応するクラスタ領域θ1と脚部に対応するクラスタ領域θ8に関する代表の移動軌跡のみを示している。図中の×は、それぞれ時刻ｔに対応するx_mの要素であり画素位置を示している。このような算出方法によれば、上述したように非線形空間上でのクラスタリングによる領域分割は、画素の動きの類似度を考慮して行われるため、単純に近接した画素の移動軌跡の時間平均を求めるような方法と比較して、動きが類似した画素の移動軌跡のみを用いて算出できるため、より高精度に代表の移動軌跡を求めることができる。このように、クラスタ領域ごとに代表の移動軌跡を求めることによって、部位ごとの動きを正確かつ簡便に表現することができる。
　次に、動き予測部は、算出した代表の移動軌跡から、時刻Ｔより先の時刻における移動体の位置を予測する。そのために、代表の移動軌跡から加速度を算出し、Ｔ＋１以降の移動体の位置を予測する。３枚以上の時系列画像が入力された場合は、次式のように代表の移動軌跡x_mごとに加速度ベクトルｓmを得ることができる。
Figure JPOXMLDOC01-appb-M000012
　ここで、ut mは動きベクトルであり、次式のように表すことができる。
Figure JPOXMLDOC01-appb-M000013
　上記式１２に示される加速度ベクトルを用いて、図１８で破線の矢印及び○で示されるように、移動体の部位ごとに、時刻Ｔ＋t´における移動体の部位位置posm(Ｔ+t´)を、以下の式１４のように、予測することができる。
Figure JPOXMLDOC01-appb-M000014
　最後に、出力部１０５は、このように予測した移動体の位置や移動体部位の位置を出力する。これにより、加速度を加味した動き予測が可能である。動きが急激に早くなったり、急激に止まったりといった場合に、その加速度を反映して移動体の位置を予測することができる。なお、上記動きベクトルの代わりにアフィンパラメータを用いてもかまわない。アフィンパラメータは、回転運動を含む動きの表現が可能であり、腕あるいは足の回旋運動の表現に適しているため、特に関節物体の位置をより正確に予測することができる。
　以上のようにして、本実施の形態及びその変形例に係る移動体検出装置及び方法では、画素に対応付けられた複数の移動軌跡間の類似度を表す距離に基づいてクラスタリングを行うことによって、画像中を移動する物体の領域を時間的に追跡した結果として、関節物体の姿勢によらずに、画像中の移動体もしくは、移動体の部位の検出、移動体を含む画像の領域分割をすることができる。また、前処理として人物候補領域を設定する必要がないため、人物候補領域の検出ミスに起因する領域分割の失敗がない。以上のように、膨大なパラメータのフィッティングを必要とせずに、非線形空間でクラスタリングを行うことによって、形状が変化しながら移動する人物等を含む画像に対しても正しく領域分割し、これによって画像中の移動体の検出を行うことが可能となる。
　以上、本発明に係る移動体検出装置及び方法について、実施の形態及び変形例を用いて説明したが、本発明は、これらの実施の形態及び変形例に限定されるものではない。上記実施の形態及び変形例に対して当業者が思いつく各種変形を施して得られる形態や、上記実施の形態及び変形例における構成要素を任意に組み合わせて得られる形態も本発明に含まれる。
　また、上記実施の形態における移動体検出装置１００は、画像入力部１０１及び動き解析部１０２を備えたが、本発明は、これらの構成要素を必須とするものではない。つまり、動画像を構成する複数のブロックのそれぞれにおける画像の移動軌跡が予め算出されている場合には、移動体検出装置１００は、外部から、そのような移動軌跡を取得し、取得した移動軌跡に対して、ステップＳ２０３～Ｓ２０８の処理を実行してもよい。
　また、本発明は、移動体検出装置として実現されたが、領域分割部１０４の機能を持つものであれば、動画像において動きをもつオブジェクトの領域を抽出、あるいは、分割する画像処理装置として実現することができるのは言うまでもない。
　本発明は、複数枚のピクチャにおける動きに基づいて、形状が変化しながら移動する人物等の移動体を含む画像を領域抽出することによって画像中の移動体を検出する移動体検出装置として、例えば、運動解析装置、監視装置、ビデオカメラやＴＶ等のＡＶ機器に内蔵させる移動体検出装置等として利用することが可能である。
　　１００　　移動体検出装置
　　１０１　　画像入力部
　　１０２　　動き解析部
　　１０３　　距離算出部
　　１０４　　領域分割部
　　１０５　　出力部
　　１０６　　測地距離算出部
　　１０７　　領域分割候補生成部
　　１０８　　領域間測地距離算出部
　　１０９　　領域分割候補選択部
　　１１０　　カメラ
　　１２０　　ディスプレイ
　１００２　　コンピュータ
　１００４　　Ｉ／Ｆ
　１００５　　ＣＰＵ
　１００６　　ＲＯＭ
　１００７　　ＲＡＭ
　１００８　　ＨＤＤ
　１００９　　ビデオカード

Claims (24)

  1. 　動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する方法であって、
    　動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出ステップと、
    　前記距離算出ステップで算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割ステップとを含み、
    　前記領域分割ステップは、
    　前記距離算出ステップで算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出ステップと、
    　前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成ステップと、
    　前記領域分割候補生成ステップで生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出ステップと、
    　前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択ステップとを含む
    　移動体検出方法。
  2. 　さらに、
    　動画像を構成する複数枚のピクチャを受け付ける画像入力ステップと、
    　前記ピクチャを構成する１個以上の画素からなるブロックごとに、時間的に隣接する２枚のピクチャ間での画像の動きを検出し、検出した動きを前記複数枚のピクチャについて連結することで、移動軌跡を算出する動き解析ステップとを含み、
    　前記距離算出ステップでは、前記動き解析ステップで算出された移動軌跡を取得し、前記距離を算出する
    　請求項１記載の移動体検出方法。
  3. 　前記距離算出ステップでは、移動軌跡間の類似度を表す前記距離として、前記複数の画像における移動軌跡間のユークリッド距離の平均値を算出する
    　請求項１記載の移動体検出方法
  4. 　前記測地距離算出ステップでは、第１の移動軌跡から第２の移動軌跡までの測地距離の算出においては、前記距離算出ステップで取得された複数の移動軌跡のいずれかを中継点として前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路のうちの最短の経路を、前記測地距離として、算出する
    　請求項１記載の移動体検出方法。
  5. 　前記測地距離算出ステップでは、
    （１）前記距離算出ステップで算出された移動軌跡間の距離に対して、その一部を無限大化することで非線形化した距離を算出し、（２）前記非線形化した距離に基づいた、第１の移動軌跡から第２の移動軌跡までの測地距離の算出において、他の移動軌跡を中継点として、前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路の距離うちの最短の距離を、前記測地距離として算出する
    　請求項４記載の移動体検出方法。
  6. 　前記測地距離算出ステップでは、複数の閾値を取得し、取得した複数の閾値を、移動軌跡の近傍を定義する閾値として用いて、前記距離算出ステップで算出された移動軌跡間の距離から、それぞれの閾値ごとに、近傍にある移動軌跡を辿っていく経路における距離を算出することで、前記移動軌跡間の測地距離を算出し、
    　前記領域分割候補生成ステップでは、前記測地距離算出ステップで算出した複数の閾値ごとの移動軌跡間の測地距離に基づいて、類似する移動軌跡の集まりを１つの領域分割候補とすることで、前記複数の領域分割候補を生成する
    　請求項１記載の移動体検出方法。
  7. 　前記測地距離算出ステップでは、前記複数の閾値として、前記距離算出ステップで算出された複数の距離のうちの最大値と最小値との間の値を生成する
    　請求項６記載の移動体検出方法。
  8. 　前記領域間測地距離算出ステップでは、前記複数の閾値のそれぞれに対して前記領域分割候補生成ステップで生成された複数の領域分割候補のセットのうちの第１の領域分割候補のセットにおける２つの領域分割候補間の領域間測地距離として、当該２つの領域分割候補における測地距離である代表測地距離と、当該第１の領域分割候補のセットに含まれる領域分割候補の総数よりも次に小さい総数だけ領域分割候補が含まれる第２の領域分割候補のセットにおける測地距離である参照測地距離とを用いて、予め定められた演算をすることで、算出する
    　請求項１記載の移動体検出方法。
  9. 　前記領域間測地距離算出ステップでは、前記参照測地距離と前記代表測地距離とに基づいて、２つの領域分割候補間の距離を表す指標と、各領域分割候補内のばらつきを表す指標とを算出し、前記距離を表す指標を、前記ばらつきを表す指標で正規化する演算をすることで、前記領域間測地距離を算出する
    　請求項８記載の移動体検出方法。
  10. 　前記領域間測地距離算出ステップで算出される領域間測地距離は、ある領域分割候補に属する複数の移動軌跡と他の領域分割候補に属する複数の移動軌跡との間の測地距離の総和から算出した２つの領域分割候補間の距離を表す指標を、前記ある領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標と、前記他の領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標とを用いて、正規化した値である
    　請求項１記載の移動体検出方法。
  11. 　前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力する
    　請求項１記載の移動体検出方法。
  12. 　前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、前記領域分割候補を選択し、前記領域分割の結果として出力する
    　請求項１記載の移動体検出方法。
  13. 　前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より大きい２つの領域分割候補を、異なる領域として選択し、前記領域分割の結果として出力する
    　請求項１２記載の移動体検出方法。
  14. 　前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より小さい２つの領域分割候補を、同一の領域として選択し、前記領域分割の結果として出力する
    　請求項１２記載の移動体検出方法。
  15. 　前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、（１）大きいほど２つの領域分割候補は異なる領域となるように、かつ、（２）小さいほど２つの領域分割候補を同一の領域となるように領域分割候補を選択し、前記領域分割の結果として出力する
    　請求項１２記載の移動体検出方法。
  16. 　前記距離算出ステップ及び前記領域分割ステップは、新たな動画像について、繰り返し実行され、
    　前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記繰り返し実行において前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力する
    　請求項１２記載の移動体検出方法。
  17. 　前記領域分割候補生成ステップでは、前記画像入力ステップで取得した画像の輝度情報に基づいて、複数の領域分割候補画像を生成し、領域分割候補画像に対応する１つ以上の移動軌跡の集まりを領域分割候補とすることで、前記複数の領域分割候補を生成する
    　請求項２記載の移動体検出方法。
  18. 　前記領域分割候補生成ステップで生成される複数の領域分割候補のうち、少なくとも１つの領域分割候補は１個の移動軌跡が属するものであり、
    　前記領域間測地距離算出ステップでは、前記１個の移動軌跡が属する領域分割候補と他の領域分割候補との領域間測地距離として、前記１個の移動軌跡と前記他の領域分割候補に属する任意の１つの移動軌跡との測地距離を出力する
    　請求項１記載の移動体検出方法。
  19. 　前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より小さい２つの移動軌跡を、同じ領域として特定する
    　請求項１８記載の移動体検出方法。
  20. 　前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より大きい２つの移動軌跡を、異なる領域として特定する
    　請求項１８記載の移動体検出方法。
  21. 　さらに、前記画像入力ステップで受け付けた動画像に対して、前記領域分割ステップで特定された領域ごとに異なる表示態様となるように、画像処理を施し、出力する出力ステップを含む
    　請求項２記載の移動体検出方法。
  22. 　さらに、前記領域分割ステップで特定された領域を構成する移動軌跡から、当該領域を代表する移動軌跡を算出し、算出した代表の移動軌跡に従って当該領域が移動すると予測することで、前記移動体の動きを予測する動き予測ステップを含む
    　請求項１記載の移動体検出方法。
  23. 　動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する装置であって、
    　動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出部と、
    　前記距離算出部で算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割部とを備え、
    　前記領域分割部は、
    　前記距離算出部で算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出部と、
    　前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成部と、
    　前記領域分割候補生成部で生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出部と、
    　前記領域分割候補生成部で生成された領域分割候補のうち、前記領域間測地距離算出部で算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択部とを有する
    　移動体検出装置。
  24. 　動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する移動体検出装置のためのプログラムであって、
    　請求項１記載の移動体検出方法に含まれるステップをコンピュータに実行させる
    　プログラム。
PCT/JP2009/006999 2009-01-09 2009-12-18 移動体検出方法および移動体検出装置 Ceased WO2010079556A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
CN200980125394.0A CN102077250B (zh) 2009-01-09 2009-12-18 移动体检测方法及移动体检测装置
US12/920,180 US8213681B2 (en) 2009-01-09 2009-12-18 Moving object detection method and moving object detection apparatus
JP2010513554A JP4542207B1 (ja) 2009-01-09 2009-12-18 移動体検出方法および移動体検出装置
EP09837446.5A EP2378485B1 (en) 2009-01-09 2009-12-18 Moving object detection method and moving object detection apparatus

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
JP2009-004083 2009-01-09
JP2009004083 2009-01-09
JP2009-209860 2009-09-10
JP2009209860 2009-09-10

Publications (1)

Publication Number Publication Date
WO2010079556A1 true WO2010079556A1 (ja) 2010-07-15

Family

ID=42316335

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2009/006999 Ceased WO2010079556A1 (ja) 2009-01-09 2009-12-18 移動体検出方法および移動体検出装置

Country Status (5)

Country Link
US (1) US8213681B2 (ja)
EP (1) EP2378485B1 (ja)
JP (1) JP4542207B1 (ja)
CN (1) CN102077250B (ja)
WO (1) WO2010079556A1 (ja)

Cited By (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2011080923A1 (ja) * 2009-12-28 2011-07-07 パナソニック株式会社 関節状領域検出装置およびその方法
CN102222157A (zh) * 2011-04-28 2011-10-19 华南理工大学 一种基于人工势场法的动态预警域生成方法
WO2012014430A1 (ja) * 2010-07-27 2012-02-02 パナソニック株式会社 移動体検出装置および移動体検出方法
WO2012101723A1 (ja) * 2011-01-26 2012-08-02 パナソニック株式会社 関節領域表示装置、関節領域検出装置、関節領域帰属度算出装置、関節状領域帰属度算出装置および関節領域表示方法
KR101313879B1 (ko) 2011-12-28 2013-10-01 대전대학교 산학협력단 기울기 히스토그램을 이용한 사람 검출 추적 시스템 및 방법
JP2013228259A (ja) * 2012-04-25 2013-11-07 Toyota Motor Corp 物体識別装置及び物体識別方法
US8605946B2 (en) 2011-03-22 2013-12-10 Panasonic Corporation Moving object detection apparatus and moving object detection method
JP2015531095A (ja) * 2012-06-06 2015-10-29 グーグル インコーポレイテッド 障害物評価技術
US9236090B2 (en) 2012-07-20 2016-01-12 Panasonic Intellectual Property Management Co., Ltd. Video generating apparatus and video generating method
JP2018106360A (ja) * 2016-12-26 2018-07-05 キヤノン株式会社 情報処理装置、情報処理方法及びプログラム
JP2020021243A (ja) * 2018-07-31 2020-02-06 グローリー株式会社 画像処理装置、画像処理方法、および、画像処理プログラム

Families Citing this family (26)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
ATE538453T1 (de) * 2008-03-14 2012-01-15 Panasonic Corp Bildverarbeitungsverfahren und bildverarbeitungsvorrichtung
US8605942B2 (en) * 2009-02-26 2013-12-10 Nikon Corporation Subject tracking apparatus, imaging apparatus and subject tracking method
CN102473307B (zh) * 2010-03-15 2015-05-27 松下电器产业株式会社 用于轨迹估计的方法和装置以及用于分割的方法
JP2011199716A (ja) * 2010-03-23 2011-10-06 Sony Corp 画像処理装置、および画像処理方法、並びにプログラム
JP2012151796A (ja) * 2011-01-21 2012-08-09 Sony Corp 画像処理装置と画像処理方法およびプログラム
KR101901958B1 (ko) * 2012-03-26 2018-11-08 한국전자통신연구원 휴리스틱 함수의 학습을 이용한 고속 경로를 탐색을 위한 장치 및 그 방법
JP2014186547A (ja) * 2013-03-22 2014-10-02 Toshiba Corp 移動物体追跡システム、方法及びプログラム
US9213901B2 (en) * 2013-09-04 2015-12-15 Xerox Corporation Robust and computationally efficient video-based object tracking in regularized motion environments
US9405974B2 (en) * 2013-11-13 2016-08-02 Xerox Corporation System and method for using apparent size and orientation of an object to improve video-based tracking in regularized environments
US11501244B1 (en) 2015-04-06 2022-11-15 Position Imaging, Inc. Package tracking systems and methods
US10148918B1 (en) 2015-04-06 2018-12-04 Position Imaging, Inc. Modular shelving systems for package tracking
US11416805B1 (en) 2015-04-06 2022-08-16 Position Imaging, Inc. Light-based guidance for package tracking systems
US10853757B1 (en) 2015-04-06 2020-12-01 Position Imaging, Inc. Video for real-time confirmation in package tracking systems
CN107798272B (zh) * 2016-08-30 2021-11-02 佳能株式会社 快速多目标检测与跟踪系统
US11436553B2 (en) 2016-09-08 2022-09-06 Position Imaging, Inc. System and method of object tracking using weight confirmation
US10634506B2 (en) 2016-12-12 2020-04-28 Position Imaging, Inc. System and method of personalized navigation inside a business enterprise
US10634503B2 (en) * 2016-12-12 2020-04-28 Position Imaging, Inc. System and method of personalized navigation inside a business enterprise
US12190542B2 (en) 2017-01-06 2025-01-07 Position Imaging, Inc. System and method of calibrating a directional light source relative to a camera's field of view
US11120392B2 (en) 2017-01-06 2021-09-14 Position Imaging, Inc. System and method of calibrating a directional light source relative to a camera's field of view
EP3853772A4 (en) 2018-09-21 2022-06-22 Position Imaging, Inc. MACHINE LEARNING ASSISTED SELF-IMPROVING SYSTEM AND METHOD FOR OBJECT IDENTIFICATION
US11089232B2 (en) 2019-01-11 2021-08-10 Position Imaging, Inc. Computer-vision-based object tracking and guidance module
DE112019007455T5 (de) * 2019-07-19 2022-03-03 Mitsubishi Electric Corporation Anzeigeverarbeitungsvorrichtung, anzeigeverarbeitungsverfahren und programm
US10911677B1 (en) * 2019-09-09 2021-02-02 Apple Inc. Multi-camera video stabilization techniques
JP7463146B2 (ja) * 2020-03-17 2024-04-08 本田技研工業株式会社 移動体監視システム、及び移動体監視方法
CN115131392B (zh) * 2022-08-31 2022-12-06 中国科学院空天信息创新研究院 基于天基光学观测图像的空间运动目标检测跟踪方法
CN119458383B (zh) * 2025-01-14 2025-03-25 浙江嘉润环保科技有限公司 基于声呐图像的恶劣环境清淤机器人路径规划方法及系统

Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH08214289A (ja) 1994-12-06 1996-08-20 Olympus Optical Co Ltd 時系列画像解析装置及びその解析方法
JPH1166319A (ja) * 1997-08-21 1999-03-09 Omron Corp 移動体検出方法及び装置並びに移動体認識方法及び装置並びに人間検出方法及び装置
JP2000222584A (ja) * 1999-01-29 2000-08-11 Toshiba Corp 映像情報記述方法、映像検索方法及び映像検索装置
JP2005332206A (ja) * 2004-05-20 2005-12-02 Nippon Hoso Kyokai <Nhk> 映像イベント判別装置及びそのプログラム、並びに、映像イベント判別用学習データ生成装置及びそのプログラム
JP2006031114A (ja) 2004-07-12 2006-02-02 Hitachi Software Eng Co Ltd 画像分割処理システム
JP2007087049A (ja) * 2005-09-21 2007-04-05 Kddi Corp 動画像処理装置
JP4456181B1 (ja) * 2008-10-27 2010-04-28 パナソニック株式会社 移動体検出方法及び移動体検出装置

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3612360B2 (ja) * 1995-04-10 2005-01-19 株式会社大宇エレクトロニクス 移動物体分割法を用いた動画像の動き推定方法
US6643387B1 (en) * 1999-01-28 2003-11-04 Sarnoff Corporation Apparatus and method for context-based indexing and retrieval of image sequences
JP4226730B2 (ja) * 1999-01-28 2009-02-18 株式会社東芝 物体領域情報生成方法及び物体領域情報生成装置並びに映像情報処理方法及び情報処理装置
US6859554B2 (en) * 2001-04-04 2005-02-22 Mitsubishi Electric Research Laboratories, Inc. Method for segmenting multi-resolution video objects
US20030123704A1 (en) * 2001-05-30 2003-07-03 Eaton Corporation Motion-based image segmentor for occupant tracking
JP4480299B2 (ja) * 2001-06-21 2010-06-16 富士通マイクロエレクトロニクス株式会社 移動体を含む画像の処理方法及び装置
US8614741B2 (en) * 2003-03-31 2013-12-24 Alcatel Lucent Method and apparatus for intelligent and automatic sensor control using multimedia database system
CN101324922B (zh) * 2008-07-30 2012-04-18 北京中星微电子有限公司 手指尖轨迹获取方法和装置

Patent Citations (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH08214289A (ja) 1994-12-06 1996-08-20 Olympus Optical Co Ltd 時系列画像解析装置及びその解析方法
JPH1166319A (ja) * 1997-08-21 1999-03-09 Omron Corp 移動体検出方法及び装置並びに移動体認識方法及び装置並びに人間検出方法及び装置
JP2000222584A (ja) * 1999-01-29 2000-08-11 Toshiba Corp 映像情報記述方法、映像検索方法及び映像検索装置
JP2005332206A (ja) * 2004-05-20 2005-12-02 Nippon Hoso Kyokai <Nhk> 映像イベント判別装置及びそのプログラム、並びに、映像イベント判別用学習データ生成装置及びそのプログラム
JP2006031114A (ja) 2004-07-12 2006-02-02 Hitachi Software Eng Co Ltd 画像分割処理システム
JP2007087049A (ja) * 2005-09-21 2007-04-05 Kddi Corp 動画像処理装置
JP4456181B1 (ja) * 2008-10-27 2010-04-28 パナソニック株式会社 移動体検出方法及び移動体検出装置

Non-Patent Citations (5)

* Cited by examiner, † Cited by third party
Title
E.W.DIJKSTRA: "A note on two problems in connexion with graphs", NUMERISCHE MATHEMATIK, 1959, pages 269 - 271, XP000837527, DOI: doi:10.1007/BF01386390
JOSHUA TENENBAUM; VIN DE SILVA; JOHN LANGFORD: "A Global Geometric Framework for Nonlinear Dimensionality Reduction", SCIENCE, vol. 290, 22 December 2000 (2000-12-22), pages 2319 - 2322
P. ANANDAN: "A Computational Framework and an Algorithm for the Measurement of Visual Motion", INTERNATIONAL JOURNAL OF COMPUTER VISION, vol. 2, 1989, pages 283 - 310, XP008055537, DOI: doi:10.1007/BF00158167
PEDRO F. FEIZENSZWALB; DANIEL P. HUTTENLOCHER: "Efficient Graph-Based Image Segmentation", INTERNATIONAL JOURNAL OF COMPUTER VISION, vol. 59, no. 2, September 2004 (2004-09-01), pages 167 - 181, XP055013351, DOI: doi:10.1023/B:VISI.0000022288.19776.77
VLADIMIR KOLMOGOROV; RAMIN ZABIH: "Computing Visual Correspondence with Occlusions via Graph Cuts", INTERNATIONAL CONFERENCE ON COMPUTER VISION, 2001

Cited By (24)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8401243B2 (en) 2009-12-28 2013-03-19 Panasonic Corporation Articulated object region detection apparatus and method of the same
JP4763863B1 (ja) * 2009-12-28 2011-08-31 パナソニック株式会社 関節状領域検出装置およびその方法
WO2011080923A1 (ja) * 2009-12-28 2011-07-07 パナソニック株式会社 関節状領域検出装置およびその方法
CN102741884B (zh) * 2010-07-27 2016-06-08 松下知识产权经营株式会社 移动体检测装置及移动体检测方法
WO2012014430A1 (ja) * 2010-07-27 2012-02-02 パナソニック株式会社 移動体検出装置および移動体検出方法
JP4979840B2 (ja) * 2010-07-27 2012-07-18 パナソニック株式会社 移動体検出装置および移動体検出方法
US8599252B2 (en) 2010-07-27 2013-12-03 Panasonic Corporation Moving object detection apparatus and moving object detection method
CN102741884A (zh) * 2010-07-27 2012-10-17 松下电器产业株式会社 移动体检测装置及移动体检测方法
JP4994525B1 (ja) * 2011-01-26 2012-08-08 パナソニック株式会社 関節領域表示装置、関節領域検出装置、関節領域帰属度算出装置、関節状領域帰属度算出装置および関節領域表示方法
CN103003846B (zh) * 2011-01-26 2016-07-06 松下知识产权经营株式会社 关节区域显示装置、关节区域检测装置、关节区域归属度计算装置、关节状区域归属度计算装置以及关节区域显示方法
CN103003846A (zh) * 2011-01-26 2013-03-27 松下电器产业株式会社 关节区域显示装置、关节区域检测装置、关节区域归属度计算装置、关节状区域归属度计算装置以及关节区域显示方法
US8929599B2 (en) 2011-01-26 2015-01-06 Panasonic Corporation Articulation region display apparatus, articulation region detecting apparatus, articulation region belongingness calculating apparatus, articulated object region belongingness calculating apparatus, and articulation region display method
WO2012101723A1 (ja) * 2011-01-26 2012-08-02 パナソニック株式会社 関節領域表示装置、関節領域検出装置、関節領域帰属度算出装置、関節状領域帰属度算出装置および関節領域表示方法
US8605946B2 (en) 2011-03-22 2013-12-10 Panasonic Corporation Moving object detection apparatus and moving object detection method
CN102222157A (zh) * 2011-04-28 2011-10-19 华南理工大学 一种基于人工势场法的动态预警域生成方法
CN102222157B (zh) * 2011-04-28 2013-10-30 华南理工大学 一种基于人工势场法的动态预警域生成方法
KR101313879B1 (ko) 2011-12-28 2013-10-01 대전대학교 산학협력단 기울기 히스토그램을 이용한 사람 검출 추적 시스템 및 방법
JP2013228259A (ja) * 2012-04-25 2013-11-07 Toyota Motor Corp 物体識別装置及び物体識別方法
JP2015531095A (ja) * 2012-06-06 2015-10-29 グーグル インコーポレイテッド 障害物評価技術
KR101763261B1 (ko) * 2012-06-06 2017-07-31 구글 인코포레이티드 장애물 평가 기법
US9236090B2 (en) 2012-07-20 2016-01-12 Panasonic Intellectual Property Management Co., Ltd. Video generating apparatus and video generating method
JP2018106360A (ja) * 2016-12-26 2018-07-05 キヤノン株式会社 情報処理装置、情報処理方法及びプログラム
JP2020021243A (ja) * 2018-07-31 2020-02-06 グローリー株式会社 画像処理装置、画像処理方法、および、画像処理プログラム
JP7130488B2 (ja) 2018-07-31 2022-09-05 グローリー株式会社 画像処理装置、画像処理方法、および、画像処理プログラム

Also Published As

Publication number Publication date
CN102077250B (zh) 2014-04-16
JP4542207B1 (ja) 2010-09-08
CN102077250A (zh) 2011-05-25
EP2378485A4 (en) 2013-07-24
JPWO2010079556A1 (ja) 2012-06-21
US8213681B2 (en) 2012-07-03
EP2378485B1 (en) 2018-04-11
US20110002509A1 (en) 2011-01-06
EP2378485A1 (en) 2011-10-19

Similar Documents

Publication Publication Date Title
JP4542207B1 (ja) 移動体検出方法および移動体検出装置
JP4456181B1 (ja) 移動体検出方法及び移動体検出装置
JP4643766B1 (ja) 移動体検出装置及び移動体検出方法
JP4782901B2 (ja) 移動体検出装置および移動体検出方法
JP4668360B2 (ja) 移動体検出方法及び移動体検出装置
JP4763863B1 (ja) 関節状領域検出装置およびその方法
JP5054206B2 (ja) 画像処理方法及び画像処理装置
JP4496992B2 (ja) 動物体アップフレーム検出方法及びプログラム及びプログラムを格納した記憶媒体及び動物体アップショット検出方法及び動物体アップフレームあるいはショット検出方法及びプログラム及びプログラムを格納した記憶媒体
JP4966946B2 (ja) 時空間画像分離装置、時空間画像分離方法および時空間画像分離プログラム

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 200980125394.0

Country of ref document: CN

WWE Wipo information: entry into national phase

Ref document number: 2010513554

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 12920180

Country of ref document: US

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 09837446

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2009837446

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: DE