Source: https://patents.google.com/patent/JPH08293028A/en
Timestamp: 2019-08-24 00:49:30
Document Index: 168844034

Matched Legal Cases: ['art 2', 'art 1', 'art 1', 'art 5', 'art 5', 'art 2']

JPH08293028A - Parallel Image clustering apparatus - Google Patents
Parallel Image clustering apparatus
JPH08293028A
JPH08293028A JP7098199A JP9819995A JPH08293028A JP H08293028 A JPH08293028 A JP H08293028A JP 7098199 A JP7098199 A JP 7098199A JP 9819995 A JP9819995 A JP 9819995A JP H08293028 A JPH08293028 A JP H08293028A
JP7098199A
Akiyoshi Wakaya
吉輝 三野
彰良 若谷
1995-04-24 Application filed by Matsushita Electric Ind Co Ltd, 松下電器産業株式会社 filed Critical Matsushita Electric Ind Co Ltd
1995-04-24 Priority to JP7098199A priority Critical patent/JPH08293028A/en
1996-11-05 Publication of JPH08293028A publication Critical patent/JPH08293028A/en
PURPOSE: To provide an image clustering device which can perform the comparison of likelihood and the updating of the cluster parameters in parallel to each other. CONSTITUTION: The image cluster parameters are stored in a cluster parameter storage part 2, and the PE 6 to 8 hold different cluster parameters. A likelihood arithmetic circuit 3 calculates the likelihood from the sample vector and the cluster parameter which are inputted via a bus 9 and stores the likelihood in a likelihood storage part 1. Then the likelihood calculated against plural sample vectors more than the number of clusters are successively compared with the likelihood stored in the part 1. The reference data are stored in a reference data storage part 5 in response to the cluster whose parameter should be updated. Every PE reads the reference data out of the part 5, changes the reference data through a reference data changing circuit 4, and stores a new parameter in the part 2.
【産業上の利用分野】本発明は、画像を複数のクラスタに分割する並列画像クラスタリング装置に関するものである。 The present invention relates to relates to a parallel image clustering apparatus for dividing an image into a plurality of clusters.
【従来の技術】近年、次世代の画像圧縮技術としてMPEG In recent years, MPEG as image compression technology of the next generation
4標準規格の議論が進んでいる。 4 discussion of standards is progressing.
【０００３】MPEG4 の実現案の一つとして、階層別圧縮方法が提案されている。 As one of MPEG4 implementation proposed hierarchical compression method has been proposed. この中で核となる技術は、動画像の中から動きのまとまったものを集めることである。 The core technology in this is to collect those coherent motion from the moving image.
【０００４】ここで扱うのは一般の自然動画像である。 [0004] is a natural moving image generally dealing with here.
この動画像の圧縮に対し、動きのまとまった物を一つのレイヤ(階層)とし、その階層毎に圧縮方法を決定し、全体としての符号量を削減しようとする。 To the compression of the moving picture, and one layer things sewn motion (hierarchy), to determine the compression method for each the hierarchy, to try to reduce the amount of code as a whole.
【０００５】レイヤは複数のクラスタから構成されている。 [0005] layer is composed of a plurality of clusters. 例えば、左から右に動いている車(レイヤ)は、座席に座っている人物、タイヤ、車体などのクラスタから構成されている。 For example, a car that is moving from left to right (layer) is composed of the person sitting in the seat, tire, from the cluster, such as the vehicle body.
【０００６】したがって、レイヤを決定するためには、 [0006] Therefore, in order to determine the layer,
各画素の輝度、色などから、その性質の近いものを集めて一つのクラスタを見つける作業が必要となる。 Brightness of each pixel, color etc., is required work to find a cluster attracting those that close in nature. これを、クラスタリングと呼ぶ。 This is referred to as clustering.
【０００７】クラスタリング手法は大きく分けて 2 つの部分からなる。 [0007] The clustering method consists of two main parts. 前半は、任意に選ばれた画素のパラメータからクラスタを構成するパラメータを求め、クラスタ構成を決定する部分である。 First half, determine a parameter in the cluster from the parameters of the pixels selected arbitrarily, a part that determines the cluster configuration.
【０００８】後半は、それぞれの画素が、決定されたクラスタのどれに属するかを決める部分である。 [0008] the second half, each of the pixels, is how in part to decide belongs to the determined clusters.
【０００９】ここでは前半の部分のみに着目する。 [0009] The attention is paid only to the portion of the first half here. 従来例を図を用いて説明する。 A conventional example will be described with reference to FIG. 図４は、特開平６−１５００ 4, Hei 6-1500
００号公報に記されている従来の並列画像クラスタリング装置である。 No. 00 is a conventional parallel image clustering apparatus are described in Japanese.
【００１０】各プロセッサは、サンプリング回路１２で選ばれた画素と各クラスタパラメータ記憶部２に格納されているパラメータとの尤度(パラメータに対するマハラノビス距離)を尤度演算回路３で計算する。 [0010] Each processor calculates the likelihood of the parameters stored in the pixel and each cluster parameter storage unit 2 selected by the sampling circuit 12 (Mahalanobis distance for the parameters) in the likelihood calculation circuit 3.
【００１１】次に各プロセッサで計算された尤度が最も大きい(マハラノビス距離が最小である)クラスタを尤度比較回路１０で選び、競合学習のデルタ規則に従い、選ばれたクラスタのパラメータを参照データ変更回路４で更新する。 [0011] Then the greatest likelihood calculated by the processor (Mahalanobis distance is minimum) to select the cluster in the likelihood comparing circuit 10, in accordance with the delta rule of competitive learning, reference parameters of the selected cluster data It is updated with the change circuit 4.
【００１２】この処理をクラスタが確定するまで繰り返す。 [0012] repeated until the cluster this process is determined. 上記の処理のうち尤度計算はプロセッサ毎に並列に行なえるが、パラメータ更新は特定のプロセッサだけで行なわれるので、この部分は逐次処理である。 Likelihood calculation is performed in parallel for each processor of the above process, since the parameter updating is performed only by a particular processor, this portion is sequentially processed.
【００１３】この処理のタイムチャートを図８に表す。 [0013] represents a time chart of this process is shown in FIG 8.
この表において尤度計算とパラメータ更新はともに２単位の時間を要するとし、尤度比較は１単位とする。 The likelihood calculating the parameter updating in the table and both require two units of time, the likelihood comparison as one unit.
【００１４】また、プロセッサ数は２とし、サンプリングを４回行なうとする。 Further, the number of the processor 2, and performed four times sampling. 図から明らかなように、３単位で尤度比較まですむが、パラメータ更新が１プロセッサで２単位時間要するので、４サンプリングを終るには、 As can be seen, but requires to likelihood compared with 3 units, so the parameter update takes 2 unit time 1 processor, the end of the 4 sampling,
合計２０単位の時間がかかる。 It takes a long time a total of 20 units.
【発明が解決しようとする課題】上記従来の並列画像クラスタリング装置の構成では、クラスタパラメータの更新が並列化されていないので、その部分の時間が全体の実行時間を遅くしている。 In the arrangement of the invention is to solve the above said conventional parallel image clustering apparatus, since update of the cluster parameters are not parallel, the time of that portion is slow overall execution time.
【００１６】本発明は、上記問題点を解決するために、 [0016] The present invention is, in order to solve the above problems,
複数のサンプリングを行なった後にまとめてパラメータ更新することにより、パラメータ更新も並列化できる並列画像クラスタリング装置を提供することを目的とする。 By parameter update together after performing a plurality of sampling, and an object thereof is to provide a parallel image clustering apparatus capable parallelized also parameter updating.
【課題を解決するための手段】上記目的を達成するために、本発明は、複数のサンプリングを行ないその尤度計算を格納する尤度記憶部を備えることにより、複数の参照データの生成を行なえる。 Means for Solving the Problems] To achieve the above object, the present invention includes the likelihood storage unit for storing the likelihood calculation performed a plurality of sampling, perform the generation of a plurality of reference data that. したがって、見かけ上並列にパラメータ更新ができるようになる。 Therefore, it becomes possible parameter update apparently parallel.
【００１８】具体的に説明すると、本発明に係る並列画像クラスタリング装置は、 （１）前記クラスタを表現するパラメータを記憶するクラスタパラメータ記憶部と、前記クラスタパラメータ記憶部の内容と外部から入力される標本データとを用いて尤度を計算する尤度演算回路と、計算された尤度を格納する尤度記憶部と、外部から入力される参照データを格納する参照データ記憶部と、前記参照データを用いて前記クラスタパラメータ記憶部の内容を更新する参照データ変更回路を備えたプロセッサをクラスタの数以上の個数備え、符号化された画素からなるフレームメモリと、 [0018] Specifically, the parallel image clustering apparatus of the present invention is input (1) and the cluster parameter storage unit that stores parameters representing the clusters, the contents and the outside of the cluster parameter storage unit a likelihood computation circuit for calculating the likelihood using the sample data, and the likelihood storage unit for storing the calculated likelihood, the reference data storing unit for storing the reference data input from the outside, the reference data a frame memory comprising several or more of the number of the cluster parameter storage unit processor cluster with reference data changing circuit for updating the contents of, consisting encoded pixels using,
前記フレームメモリからランダムに画素情報を読み出すサンプリング回路を備え、前記サンプリング回路から出力される標本データを前記複数のプロセッサに入力し、 The random comprises a sampling circuit for reading pixel information from the frame memory, enter the sample data output from the sampling circuit to the plurality of processors,
前記プロセッサの前記尤度演算回路からの出力を比較し、尤度が最も大きいクラスタを選択する尤度比較回路を備え、前記尤度比較回路から出力される参照データを選択された前記プロセッサに入力することを特徴とするするものである。 Comparing the output from the likelihood calculating circuits of the processor, including a likelihood comparing circuit for selecting the largest cluster likelihood is input to the processor the reference data is selected to be output from the likelihood comparing circuit it is to be characterized by. （２）画像を複数の部分画像に分割し、分割された画像の符号化された画素の部分集合を記憶するサブフレームメモリと、前記サブフレームメモリからランダムに画素情報を読み出すサンプリング回路と、前記クラスタを表現するパラメータを記憶する複数のクラスタパラメータ記憶部と、前記クラスタパラメータ記憶部の内容と前記サンプリング回路から出力される標本データとを用いて尤度を計算し、前記尤度が最も大きいクラスタを選択する尤度演算比較回路と、前記尤度演算比較回路から出力された変更データを格納する変更データ記憶部と、外部から入力される参照データを格納する参照データ記憶部と、前記参照データを用いて前記クラスタパラメータ記憶部の内容を更新する参照データ変更回路を備えたプロセッサを分割画面 (2) dividing the image into a plurality of partial images, and the sub-frame memory for storing a subset of the encoded pixels of the divided image, a sampling circuit for reading randomly pixel information from said sub-frame memory, wherein a plurality of clusters parameter storage unit for storing parameters representing the cluster, the cluster parameters the contents of the storage unit by using the sample data output from the sampling circuit to calculate the likelihood, the likelihoods largest cluster a likelihood computation comparator circuit for selecting, and changing the data storage unit for storing the modified data output from the likelihood calculation comparator circuit, a reference data storage unit that stores reference data which is input from outside, said reference data split screen processor with reference data changing circuit for updating the contents of the cluster parameter storage unit by using the 以上の個数備え、前記プロセッサから出力された参照データを全ての前記プロセッサの前記変更データ記憶部に送信する通信路を備えることを特徴とするするものである。 With number above, it is to be characterized in that it comprises a communication path for transmitting the reference data output from the processor to the change data storing unit of all the processors. （３）画像を複数の部分画像に分割し、分割された画像の符号化された画素の部分集合を記憶するサブフレームメモリと、前記サブフレームメモリからランダムに画素情報を読み出すサンプリング回路と、前記クラスタを表現するパラメータを記憶する複数のクラスタパラメータ記憶部と、前記クラスタパラメータ記憶部の内容と前記サンプリング回路から出力される標本データとを用いて尤度を計算し、前記尤度が最も大きいクラスタを選択する尤度演算比較回路と、前記尤度演算比較回路から出力された変更データを格納する変更データ記憶部と、外部から入力される参照データを格納する参照データ記憶部と、前記参照データを用いて前記クラスタパラメータ記憶部の内容を更新する参照データ変更回路を備えたプロセッサを分割画面 (3) dividing the image into a plurality of partial images, and the sub-frame memory for storing a subset of the encoded pixels of the divided image, a sampling circuit for reading randomly pixel information from said sub-frame memory, wherein a plurality of clusters parameter storage unit for storing parameters representing the cluster, the cluster parameters the contents of the storage unit by using the sample data output from the sampling circuit to calculate the likelihood, the likelihoods largest cluster a likelihood computation comparator circuit for selecting, and changing the data storage unit for storing the modified data output from the likelihood calculation comparator circuit, a reference data storage unit that stores reference data which is input from outside, said reference data split screen processor with reference data changing circuit for updating the contents of the cluster parameter storage unit by using the 以上の個数備え、前記プロセッサから出力された参照データを指定された前記プロセッサの前記変更データ記憶部に送信する通信路を備え、前記指定されたプロセッサの前記参照データ変更回路において前記クラスタパラメータ記憶部の内容を更新した後、前記通信路を用いて全ての前記プロセッサの前記参照データ記憶部に送信し、全ての前記プロセッサは前記クラスタパラメータの内容を前記参照データ記憶部の内容に置き換えることを特徴とするするものである。 With number above, a communication channel to be transmitted to the change data storing unit of the processor specified reference data output from the processor, wherein the in the reference data changing circuit for the specified processor clusters parameter storage unit after updating the contents of, and transmitted to the reference data storage unit of any of said processor using said channel, all of the processor, wherein the replacing the contents of the cluster parameters on the content of the reference data storage unit it is intended to be a.
（１）アルゴリズムの後半であるクラスタパラメータの更新も並列にできるので、全体としてクラスタ数に比例した並列度を持つ並列画像クラスタリング装置を提供できる。 (1) it is possible in parallel also updates the cluster parameter is a second half of the algorithm, can provide a parallel image clustering apparatus having a parallelism in proportion to the number of clusters as a whole. （２）クラスタ数よりも高い並列度である画素並列で尤度計算を行なえるので、より高い並列度を持つ並列画像クラスタリング装置を提供できる。 (2) Since perform the likelihood calculated by the pixel parallel a higher degree of parallelism than the number of clusters, it is possible to provide a parallel image clustering apparatus having a higher degree of parallelism. （３）尤度計算は画素並列で行ない、パラメータ更新はクラスタ並列で行なうので、さらに高い並列度を持つ並列画像クラスタリング装置を提供できる。 (3) the likelihood calculation is performed in the pixel parallel, parameter updating is performed at the cluster parallel, it can provide a parallel image clustering apparatus having a higher degree of parallelism.
【実施例】以下本発明の実施例の並列画像クラスタリング装置について、図面を参照しながら説明する。 Parallel image clustering apparatus of the embodiment of EXAMPLES Hereinafter the present invention will be described with reference to the drawings.
【００２１】図１は本発明の実施例１における並列画像クラスタリング装置の概略構成図を示すものである。 [0021] FIG. 1 shows a schematic configuration diagram of a parallel image clustering apparatus in the first embodiment of the present invention.
【００２２】図１において、１１は画像情報を格納するフレームメモリであり、１２はフレームメモリからランダムに画素情報を取り出すサンプリング回路である。 [0022] In FIG. 1, 11 is a frame memory for storing image information, 12 is a sampling circuit for taking out a random pixel information from the frame memory. ２ 2
はクラスタのパラメータを格納するクラスタパラメータ記憶部で、３はクラスタパラメータ記憶部２に格納されているパラメータとサンプリング回路１２から通信路９ The cluster parameter storage unit for storing the parameters of a cluster, the channel 9 3 From the parameters and sampling circuit 12 that is stored in the cluster parameter memory 2
を経て入力された標本データから尤度を計算する尤度演算回路である。 A likelihood calculating circuit for calculating the likelihood from the input sample data through.
【００２３】計算された尤度は一旦尤度記憶部１に格納され、複数のサンプリングが終了した後に出力される。 The calculated likelihood is once stored in the likelihood storage unit 1 is output after a plurality of sampling is completed.
【００２４】１０は各プロセッサで計算された尤度を入力し、最も大きな尤度を持つプロセッサを選択してそのプロセッサに参照データを送信する尤度比較回路である。 [0024] 10 inputs the likelihood calculated by each processor, a likelihood comparing circuit for transmitting reference data to the processor to select a processor with the greatest likelihood.
【００２５】各プロセッサは尤度比較回路１０からの入力を、一旦、参照データ記憶部５に格納し、全ての比較が終了した後に、参照データ変更回路４によってクラスタパラメータ記憶部２の内容を更新する。 [0025] The input from each processor likelihood comparing circuit 10, temporarily stored in the reference data storage unit 5, after all the comparison is completed, updates the contents of the cluster parameter storage unit 2 by the reference data change circuit 4 to.
【００２６】つまり、複数のサンプリング行なった後にパラメータ更新するので、平均すると各プロセッサで並列にパラメータ更新が行なえる。 [0026] That is, since the parameter update after performing a plurality of sampling, averaging the enable parameter updating in parallel with each processor.
【００２７】この様子を図５のタイムチャートを使って説明する。 [0027] will be described with reference to the time chart of FIG. 5 this state. 従来例の場合と同様に、尤度計算とパラメータ更新はともに２単位の時間を要するとし、尤度比較は１ 単位とする。 As with the prior art, the likelihood calculation and parameter updating is to require both 2 units of time, the likelihood comparison as one unit.
【００２８】また、プロセッサ数は２とし、サンプリングを４回行なうとする。 Further, the number of the processor 2, and performed four times sampling. 図から明らかなように、尤度計算を４回まず行ない、その後比較し、パラメータ更新を行なう。 As apparent from FIG. Performs first 4 times the likelihood calculations, and then compared, performs parameter update. パラメータ更新が並列に行なえているので、その分、実行時間が短くなっている。 Since the parameter updates are performed in parallel, correspondingly, execution time is reduced. 従来例で２０単位必要だった実行時間が、本実施例では、１６単位で行なえるようになっている。 20 units needed running time in the conventional example, in this embodiment, it has become so performed in 16 units.
【００２９】図２は本発明の実施例２における並列画像クラスタリング装置の概略構成図を示すものである。 FIG. 2 shows a schematic diagram of a parallel image clustering apparatus in the second embodiment of the present invention.
【００３０】図２において、１００は分割された画像情報を格納するサブフレームメモリであり、１０１はサブフレームメモリ１００からランダムに画素情報を取り出すサンプリング回路である。 [0030] In FIG. 2, 100 is a sub-frame memory for storing image information divided, 101 is a sampling circuit for taking out a random pixel information from the sub-frame memory 100. 本実施例では尤度計算は画素毎に行なうので、画像はサブフレームメモリ１００にプロセッサ毎に分有して保持している。 In this embodiment, since the likelihood calculation is performed for each pixel, the image retains in Bun'yu per processor in the sub-frame memory 100.
【００３１】１０２はクラスタのパラメータを格納するクラスタパラメータ記憶部で、全クラスタのパラメータを持ち、その内容は各プロセッサで共通である。 [0031] 102 in the cluster parameter storage unit for storing the parameters of the clusters has a parameter of all clusters, the contents of which are common to the processors. １０３ 103
はクラスタパラメータ記憶部１０２に格納されているパラメータとサンプリング回路１０１から出力された標本データから尤度を計算し、尤度の最も大きいものを出力する尤度演算比較回路である。 The likelihood is calculated from the outputted sample data from the parameter and the sampling circuit 101 are stored in the cluster parameter storage unit 102, a likelihood calculation comparison circuit for outputting the largest likelihood.
【００３２】比較された尤度は一旦変更データ記憶部１ [0032] comparative likelihood once change data storage unit 1
０５に格納される。 It is stored in the 05. 変更データは通信路１０７を経て、 Change data via a communication path 107,
全プロセッサの参照データ記憶部１０６にブロードキャストされ、参照データ変更回路１０４によりクラスタパラメータ記憶部１０２の内容が変更される。 Is broadcast in the reference data storage unit 106 of all the processors, the content of the cluster parameter storage unit 102 is changed by the reference data changing circuit 104.
【００３３】つまり、尤度計算はプロセッサ間で画素毎に並列に行なわれ、比較もプロセッサ内で行なわれる。 [0033] That is, the likelihood calculations are performed in parallel for each pixel between processors, compared also performed in a processor.
さらに、パラメータ更新は、参照データが全プロセッサにブロードキャストされるた後、プロセッサ内で逐次に行なわれる。 Further, the parameter update reference data after being broadcast to all the processors is performed sequentially in the processor.
【００３４】この様子を図６のタイムチャートを使って説明する。 [0034] will be described with reference to the time chart of FIG. 6 this state. 変更データのブロードキャストには１単位の時間がかかるものとする。 The broadcast change data shall take time for one unit.
【００３５】ここでは、４サンプリングを同時に行なう場合を考え、プロセッサ数は４とし、クラスタ数は２であるとする。 [0035] Here, consider the case of performing 4 sampling time, number of processors is four and the number of clusters is 2.
【００３６】各プロセッサは最初の２単位で尤度計算を行ない、次の４単位時間でその比較結果が順にブロードキャストされる。 [0036] Each processor performs likelihood calculation in the first two units, the comparison result in the next 4 time unit are sequentially broadcast. その後のパラメータ更新は４変更データ分が各プロセッサ内で逐次に行なわれるので、８単位時間かかる。 Since subsequent parameter updates 4 changed data content is sequentially performed in each processor, it takes 8 unit time. 以上を合計すると、１４単位の時間が必要である。 The total of the above, time is required for 14 units.
【００３７】これは、従来例で必要だった２０単位に比べ大きく改善されているといえる。 [0037] This is said to be significantly improved compared to the 20 units that were required by the prior art. 図３は本発明の実施例３における並列画像クラスタリング装置の概略構成図を示すものである。 Figure 3 shows a schematic configuration diagram of a parallel image clustering apparatus in the third embodiment of the present invention.
【００３８】図３は図２とほぼ同じであり、相違点は、 [0038] Figure 3 is substantially the same as FIG. 2, difference,
参照データ変更回路１０４での変更情報が再び変更データ記憶部に送られ、全プロセッサにブロードキャストされる点が異なる。 Change information in the reference data changing circuit 104 is sent to the change data storing unit again, that it is broadcast to all the processors are different.
【００３９】尤度計算を行なう部分までは実施例２の場合と全く同じであるが、その後のパラメータ更新の方法が異なる。 [0039] While up part for likelihood calculation is exactly the same as in Example 2, are different ways subsequent parameter update. 尤度演算比較回路１０３から出力された変更データは一旦変更データ記憶部に格納され、通信路１０ Change data output from the likelihood computation comparator circuit 103 is once stored in the modification data storing unit, a communication path 10
７を経て、変更されるべきクラスタを担当するプロセッサの参照データ記憶部１０６に送られる。 7 through, is sent to a reference data storage unit 106 of the processor in charge of the cluster to be changed. 例えば、クラスタ１はプロセッサ１、クラスタ２はプロセッサ２とする。 For example, cluster 1 processor 1, cluster 2 and the processor 2.
【００４０】プロセッサ１では、参照データ記憶部１０ [0040] In the processor 1, the reference data storage unit 10
６から参照データを読みだし、参照データ変更回路１０ Reads the reference data from the 6, the reference data changing circuit 10
４によりクラスタパラメータ記憶部１０２のクラスタ１ 4 by the cluster of the cluster parameter storage unit 102
の内容のみの変更を行なう。 Of performing the change of only the contents. プロセッサ２は、クラスタ２の変更のみを行なう。 Processor 2 performs only the changes of cluster 2.
【００４１】変更された内容は、再度変更データ記憶部１０５に送られ、全プロセッサの参照データ記憶部１０ The changed content is sent to change the data storage unit 105 again, the reference data storage unit 10 of all processors
６に送られた後、各プロセッサは送られてきたクラスタパラメータをそのままクラスタパラメータ記憶部１０２ After sent to 6, each processor cluster parameters sent as cluster parameter storage unit 102
【００４２】この様子を図７のタイムチャートを使って説明する。 [0042] will be described with reference to the time chart of FIG. 7 this situation. 実施例２の場合と同様に、変更データのブロードキャストには１単位の時間がかかるものとし、１対１通信も同様に１単位かかるとする。 As in Example 2, it is assumed that it takes time for one unit to broadcast the modified data, and one-to-one communication likewise takes one unit.
【００４３】ここでも、４サンプリングを同時に行なう場合を考え、プロセッサ数は４とし、クラスタ数は２であるとする。 [0043] Again, consider the case of performing 4 sampling time, number of processors is four and the number of clusters is 2.
【００４４】各プロセッサは最初の２単位で尤度計算を行ない、次の４単位時間でその比較結果を担当するプロセッサに１対１通信で送る。 [0044] Each processor performs likelihood calculation in the first two units, sending on a one-to-one communication processor in charge of the comparison result in the next 4 time unit. その後のパラメータ更新はプロセッサ１と２で２個ずつ行なわれるので、４単位時間かかる。 Since subsequent parameter update is performed every two by the processor 1 and 2, it takes four unit time. さらに、更新されたクラスタパラメータをプロセッサ１と２からブロードキャストされる。 Furthermore, it broadcast the updated cluster parameters from the processor 1 and 2.
【００４５】これは２単位の時間がかかる。 [0045] This takes 2 units of time. 以上を合計すると、１２単位の時間が必要である。 The total of the above, it is necessary to 12 units of time.
【００４６】これは、従来例で必要だった２０単位に比べ大きく改善されており、実施例１、２、３を通して最も小さくなっている。 [0046] It is greatly improved compared to 20 units was required in the conventional example, the smallest through third embodiments.
【発明の効果】本発明は、上記した構成により、尤度計算だけでなく、クラスタパラメータの更新も並列に行なえる。 According to the present invention, the configuration described above, not only the likelihood calculation, performed in parallel also updates the cluster parameter. また、クラスタ並列よりも並列度の高い画素並列を実現することができる。 Further, it is possible to realize a pixel parallel high parallelism than the cluster parallel.
【図１】本発明の実施例１における並列画像クラスタリング装置の概略構成図 Schematic block diagram of a parallel image clustering apparatus in Embodiment 1 of the present invention
【図２】本発明の実施例２における並列画像クラスタリング装置の概略構成図 Schematic block diagram of a parallel image clustering apparatus in the second embodiment of the present invention; FIG
【図３】本発明の実施例３における並列画像クラスタリング装置の概略構成図 Schematic block diagram of a parallel image clustering apparatus in the third embodiment of the present invention; FIG
【図４】従来例の並列画像クラスタリング装置の概略構成図 Figure 4 is a schematic block diagram of a parallel image clustering apparatus of the prior art
【図５】本発明の実施例１におけるタイムチャート The time chart in Example 1 of the present invention; FIG
【図６】本発明の実施例２におけるタイムチャート Figure 6 is a time chart in the second embodiment of the present invention
【図７】本発明の実施例３におけるタイムチャート The time chart in Example 3 of the present invention; FIG
【図８】従来例のタイムチャート [8] conventional time chart of
【請求項１】同じ特徴を持つ画素の集合をクラスタとし、複数の前記クラスタからなる画像に対し、 前記クラスタを表現するパラメータを記憶するクラスタパラメータ記憶部と、前記クラスタパラメータ記憶部に記憶されたクラスタのパラメータと、外部から入力される標本データとを用いて尤度を計算する尤度演算回路と、計算された尤度を格納する尤度記憶部と、外部から入力される参照データを格納する参照データ記憶部と、 [Claim 1] with a set of pixels having the same characteristics as the cluster, the image comprising a plurality of the clusters, and the cluster parameter storage unit that stores parameters representing the clusters stored in the cluster parameter storage unit storage cluster and parameters, and the likelihood calculation circuit for calculating the likelihood using the sample data inputted from the outside, and the likelihood storage unit for storing the calculated likelihood, the reference data input from the outside a reference data storage unit that,
前記参照データを用いて前記クラスタパラメータ記憶部の内容を更新する参照データ変更回路とを備えた複数個のプロセッサと、 符号化された画素情報を記憶するフレームメモリと、 前記フレームメモリからランダムに画素情報を読み出すサンプリング回路と、尤度比較回路とを備え、 前記サンプリング回路から出力される標本データを前記複数のプロセッサに入力し、 前記尤度比較回路で、前記プロセッサの前記尤度演算回路からの出力を比較し、尤度が最も大きいクラスタを選択し、 前記尤度比較回路から出力される参照データを選択された前記プロセッサに入力することを特徴とする並列画像クラスタリング装置。 A plurality of processors and a reference data changing circuit for updating the contents of the cluster parameter storage unit by using the reference data, a frame memory for storing pixel information encoded, randomly pixel from the frame memory a sampling circuit for reading information, and a likelihood comparing circuit, enter the sample data output from the sampling circuit to the plurality of processors, in the likelihood comparing circuit, from the likelihood calculating circuits of the processor compare the output, select the highest cluster likelihood is, the parallel image clustering apparatus characterized by inputting to the processor a reference data has been selected to be output from the likelihood comparing circuit.
【請求項２】同じ特徴を持つ画素の集合をクラスタとし、複数の前記クラスタからなる画像に対し、 画像を複数の部分画像に分割し、分割された画像の符号化された画素の部分集合を記憶するサブフレームメモリと、前記サブフレームメモリからランダムに画素情報を読み出すサンプリング回路と、前記クラスタを表現するパラメータを記憶する複数のクラスタパラメータ記憶部と、前記クラスタパラメータ記憶部の内容と前記サンプリング回路から出力される標本データとを用いて尤度を計算し、前記尤度が最も大きいクラスタを選択する尤度演算比較回路と、前記尤度演算比較回路から出力された変更データを格納する変更データ記憶部と、外部から入力される参照データを格納する参照データ記憶部と、前記参照データを用いて前記ク Wherein the set of pixels having the same characteristics as the cluster, the image comprising a plurality of said cluster, an image is divided into a plurality of partial images, a subset of the encoded pixels of the divided images and the sub-frame memory for storing a sampling circuit for reading randomly pixel information from said sub-frame memory, and a plurality of clusters parameter storage unit that stores parameters representing the clusters, and the contents of the cluster parameter storage unit said sampling circuit by using the sample data output from the estimation section, and likelihood computation comparator circuit for selecting the likelihood is greatest cluster, changing data stored modified data output from the likelihood calculation comparison circuit a storage unit, a reference data storage unit that stores reference data which is input from outside, the click using the reference data ラスタパラメータ記憶部の内容を更新する参照データ変更回路とを備えた複数個のプロセッサと、 前記プロセッサから出力された参照データを全ての前記プロセッサの前記変更データ記憶部に送信する通信路とを備えた並列画像クラスタリング装置。 Comprising a plurality of processors and a reference data changing circuit for updating the contents of the raster parameter storage unit, a communication channel and for transmitting the reference data output from the processor to the change data storing unit of all of said processor parallel image clustering apparatus.
【請求項３】同じ特徴を持つ画素の集合をクラスタとし、複数の前記クラスタからなる画像に対し、 画像を複数の部分画像に分割し、分割された画像の符号化された画素の部分集合を記憶するサブフレームメモリと、前記サブフレームメモリからランダムに画素情報を読み出すサンプリング回路と、前記クラスタを表現するパラメータを記憶する複数のクラスタパラメータ記憶部と、前記クラスタパラメータ記憶部の内容と前記サンプリング回路から出力される標本データとを用いて尤度を計算し、前記尤度が最も大きいクラスタを選択する尤度演算比較回路と、前記尤度演算比較回路から出力された変更データを格納する変更データ記憶部と、外部から入力される参照データを格納する参照データ記憶部と、前記参照データを用いて前記ク Wherein the set of pixels having the same characteristics as the cluster, the image comprising a plurality of said cluster, an image is divided into a plurality of partial images, a subset of the encoded pixels of the divided images and the sub-frame memory for storing a sampling circuit for reading randomly pixel information from said sub-frame memory, and a plurality of clusters parameter storage unit that stores parameters representing the clusters, and the contents of the cluster parameter storage unit said sampling circuit by using the sample data output from the estimation section, and likelihood computation comparator circuit for selecting the likelihood is greatest cluster, changing data stored modified data output from the likelihood calculation comparison circuit a storage unit, a reference data storage unit that stores reference data which is input from outside, the click using the reference data ラスタパラメータ記憶部の内容を更新する参照データ変更回路とを備えた複数個のプロセッサと、 前記プロセッサから出力された参照データを指定された前記プロセッサの前記変更データ記憶部に送信する通信路とを備え、 前記指定されたプロセッサの前記参照データ変更回路において前記クラスタパラメータ記憶部の内容を更新した後、前記通信路を用いて全ての前記プロセッサの前記参照データ記憶部に送信し、全ての前記プロセッサは前記クラスタパラメータの内容を前記参照データ記憶部の内容に置き換えることを特徴とする並列画像クラスタリング装置。 A plurality of processors and a reference data changing circuit for updating the contents of the raster parameter storage unit, a communication channel and to transmit the changed data storage unit of the processor specified output referenced data from the processor comprising, after updating the contents of the cluster parameter storage unit in the reference data change circuit of said specified processor, and transmitted to the reference data storage unit of any of said processor using said channel, all of the processors parallel image clustering apparatus characterized by replacing the contents of the cluster parameters on the content of the reference data storage unit.
JP7098199A 1995-04-24 1995-04-24 Parallel Image clustering apparatus Pending JPH08293028A (en)
JP7098199A JPH08293028A (en) 1995-04-24 1995-04-24 Parallel Image clustering apparatus
US08/636,114 US5909508A (en) 1995-04-24 1996-04-22 Parallel image-clustering apparatus
JPH08293028A true JPH08293028A (en) 1996-11-05
JP7098199A Pending JPH08293028A (en) 1995-04-24 1995-04-24 Parallel Image clustering apparatus
GB1243969A (en) * 1967-11-15 1971-08-25 Emi Ltd Improvements relating to pattern recognition devices
1995-04-24 JP JP7098199A patent/JPH08293028A/en active Pending
1996-04-22 US US08/636,114 patent/US5909508A/en not_active Expired - Fee Related
US5909508A (en) 1999-06-01
JP4056398B2 (en) 2008-03-05 Method for generating a FinFET shape, the program, and, the system
CN1307599C (en) 2007-03-28 Image Matching
DE602004009591T2 (en) 2008-07-24 Differential coding a 3D graphics processor by using
CN1039957C (en) 1998-09-23 Video insertion processing system