公知のラベリング処理アルゴリズム

2月 6th, 2010 by tune No comments »

ラベリング処理というのは入力画像に対して、連結する画素(同じ色とか、同じ領域とか)ごとに同じ番号を割り振る処理のことです。領域別に処理する際の前処理に使ったり、画像中の微小領域のサイズを測定してノイズ除去に使ったりと色々と有用です。アルゴリズム入門 : 第 3 章 画像処理入門 1を読むとイメージが湧くかと思います。
ラベリング処理のイメージ図

ラベリング処理は1970年代から知られている処理ですが、高速なアルゴリズムが意外と知られていません。ネットで検索すると大学の授業での説明資料が見つかる程度で、文献をあたっても解説があまりにも少なく多くは役に立ちません。

古い本でラベリング処理のアルゴリズムが詳しく説明されたものを見つけたので多くの人に有用と思い、ここに書いておきます。参考にした本は近代科学社発行の長尾真さんによる「デジタル画像処理」で、1978年に発行されています。ラベリング処理の紹介は360ページ〜361ページに有ります。

1:値を隣接する画素に伝搬させる

Sの成分をラベル付けする簡単な手続きは、探索と”伝搬”からなるものである。1が見つかるまでSを走査し、その値をまだ使われてない最初のラベルの値、たとえばvに変える。そしてvを1に向けて繰り返し(必要なら並列に)伝搬させる。すなわち、vを近傍として持つ1をvに変える。もはや変化の可能性がなくなったとき、明らかに最初のvに連結した1は全てvになっている。ここでさらに走査を続ける。別の1が見つかれば、これはv成分には属してないので、新しいラベルを付けて同じ手続を繰り返す。

Sが処理対象の画像、ラベル付けする対象が1、割り振るラベル値がvです。
この手法は「この手続は簡単ではあるが、非常に時間がかかる。各々の伝搬の過程は、たとえ並列に処理しても、図形の面積の次数だけの反復を要するからである。」と紹介されています。最初に紹介したMSのサイトで使われているのがまさにこれです。おすすめできません。

2:境界線を抽出し、輪郭内部に同一の値を割り振る

成分のラベル付けの別な方法としては、9.1.2節で述べた境界を見つける手法を、いくつかの外側境界(すなわち、Sの成分でこれを囲むS^の成分に隣接している境界。演習9参照)を別々にマークを付けるよう修正し、各成分の外側境界に異なったラベルを用いる。これが済むと、必要に応じて外側境界のラベルを成分の内側へ”伝搬”させることができる。これを並列に行うなら、たかだか図形の半径に等しい反復数を要する。

手当たりしだいに伝搬させるのではなく、まずは領域の輪郭にユニークなラベル番号を付与し、必要であれば内側に値をコピーする。1番よりは効率的ですが、「外側境界のラベル付けの手続きは時間がかかる
」処理であり、図形の面積につれて増加する多数のステップを有します。

3:行毎に横のつながり(ラン)を求め、上下の対照表をもとにつなげて行く

たいていの目的には、境界よりむしろ1のランを追跡してラベル付けをする次の手法が最良策である。図形の第1行目において、各ランに異なったラベルを与える。第2(とそれ以下の)行では、1のランを調べて前行のランと位置を比べる。ランρが前行のどのランとも隣接していなければρに新しいラベルを付ける。ρが前行のちょうど1つのランに隣接しているなら、そのランのラベルを付ける。ρが前行の2つ以上のランに隣接しているなら、ρにはこれらのらべるの(たとえば)最小値を付けるが、これらのラベルはすべて同一成分に属することも控えておく。図形がこのようにしてすべて走査されたとき、控えを分類して等しいラベルの集まりを決定できる。必要なら、図形を再走査し各ラベルを、たとえば等価な最小の値のラベルに置き換えることが出来る。

ということで、3番目がおすすめです。処理時間が画像サイズに依存して決まるし、ラスタ走査のみなのでメモリ上のキャッシュも有効に動いてくれるでしょう。

上の説明文を素直に実装すれば効率のよいラベリング処理を実現出来るでしょう。

その他心に残った話 – JaSST’10 Tokyo

1月 31st, 2010 by tune No comments »

◯コードの共同所有のやり方
共同所有をすると品質向上、リスクの低減、チームの自己組織化、メンバの安心度につながるが、どうすれば実現出来るのか。

最初は物理的な共有、svnやgitなどのツールの活用がこれに当たります。
次は知識の共有、ペアプロやレビュー、TDDなどの取り組みがこれに当たります。
最後が責任の共有、リファクタリングの実施やCIがこれに当たります。

単にコードを共有しましょうというよりも段階を見せて、効果を説得しないと駄目ですね。社内で使わせていただきます。

◯オフショアで成功するコツ
工程ではなく、機能で委託する。機能単位で責任を持ってもらうことが出来る。
例えばテスト工程だけオフショアに出すと、高い確率でレベルが低い人材が割り当てられる。

アメリカではオフショアをかなりやめているらしい。5割から6割を国内に戻したらしい。結論としては「オフショアはうまく行かない。」という認識が広まっている。(ハーバードビジネスレビューで見たとか?)
オフショアするのは企業が重要視してないところ、テストをオフショアする企業は結局「テストを軽視している」ということ。

あとは人が辞めてしまうので、仕組みにノウハウがたまるようにしないとだめだとNEC誉田さんからコメント。
品質の期待値をきちんと伝えるのも効果があるらしい。

◯オフショア開発におけるテスト改善
事例発表でTISの鈴木三紀夫さんが「890個のテスト観点リストと745個の不具合推測リスト」を作成したと話していた。こんなにたくさんのリストを見きれるのかという疑問がすぐ頭をよぎるが、全部読むことが重要ではなく「作業者に頭を使わせることが大事」とのこと。数が膨大だと作業者がコピペで済ませることができなくなり、担当者なりに頭を使う必要が必ず生じる。

・・・

基調講演と招待講演は大変タメになりましが、その他のセッションは役に立ちそうなものと、役に立たなそうなものと結構はっきり分かれました。
参加費は2日間で8000円ぐらいでしたが、値段的にはこんなものでしょう。学会の延長線上と思えば。
でも来月同じ雅叙園で開かれるデブサミを考えるとデブサミのほうがおすすめかも知れません。

来年は誰か他の人に行ってもらおうかな。

品質という王道を行こう – JaSST’10 Tokyo 招待講演

1月 31st, 2010 by tune No comments »

NECの誉田直美さんが、自信が考える品質のあり方について語った90分のメモです。

・・・

誉田さんが考える「王道を行く」とは本質を理解した上で、決意を持ち達成に向けて行動すること。
手段ではなく目的、手抜きではなく効率化、新たな気持も大事だけど先人の知恵に学ぶ。
品質のみを追求している訳ではないが、品質を追求すればコストも納期も改善出来ると誉田さんは考えている。

<事例1>
自社が関連する単体テスト実施状況を調査したところ、単体テストをきちんと実施しているプロジェクト(限界値とか、テストの組み合わせを考慮して普通にやる)は単体テストで手抜きをしている or 単体テストをしていないプロジェクトと比較して出荷後のバグが38%少なかった。きちんとテストを実施すれば62%も取り除けたのに(きちんと単体テストをしても38%も残るのかという見方もできるけど・・・これは私の主観)

<事例2>
オフショアの品質を改善するために、海外子会社をかなりの労力をかけて教育した。具体的には数値目標を立て、プロセス・基礎開発技術・マネジメント・日本語語学力に国内同等レベルを求めた。結果として現地管理職の認識も代わり、改善が進むようになった。(最も、事例としてあげた中国の工場は管理者が転職してしまったらしいんだけど・・・)

<事例3>
開発案件や組織力が似ている組織Aと組織Bからいろいろなデータを取ってみた。Aを100%としたとき、Bの全工数は106%程度、ただしレビューやテストは50%前後だった。1000行あたりのバグ件数はBはAの80%。全バグ数に対する上流工程までのバグ摘出率はAとBはほぼ同じ。Bのテスト項目数はAの約半分だった。

組織Bは「プロセスを改善すれば工数やバグ数は減るはず」と解釈し、そのように取り組んでいた。だからテスト工数がAより少なくなり、そのような統計結果も出た。でも市場で出たバグを見るとBの方が品質が悪かった(数は変わらなくても、Bの方が長期間にわたってバグが出続けた!)。結果としてBのほうがAより2倍以上品質が悪いという調査結果が出た。

データを分析すると組織の取り組み方の違いが現れた。Bの組織は目標の達成が主眼となってしまい、数値目標を達成したらテストを終えてしまっていた。本当はプロジェクトごとに差が出るものなのにそれがなかった。基準値順守が「形骸化」してしまった。社内のベストプラクティスを組織Aと組織Bに適用しても組織Bでは効果が得られなかった。結局組織Bはルールだから実施していた、テスト時に担当者が頭を使っていなかった。

誉田さんがまとめのスライドに載せていたのは「何のためのプロセスかを常に考える土壌作り」が必要とのこと。形だけを真似ても成果は得られない。

・・・

目から鱗でしたね。ソフトウェアの状態をツールやメトリクスを使って見える化し、データをノウハウとして蓄え、組織として横展開できれば品質は今より良くなるはずだと思っていましたから。まさに組織Bの人間です。
プロジェクトごとに性格や条件が違うことに気づき、もっと頭を使わないと駄目ですね。自社の品質改善を考えていくに当たり、大きな宿題をもらった講演でした。

Successful Software Management: 17 Lessons Learned – JaSST’10 Tokyo 基調講演

1月 30th, 2010 by tune No comments »

1/28と1/29に目黒雅叙園で開催されていたJaSST’10に行ってきました。色々学んだことはあったのですが、まずは基調講演の振り返りから。基調講演はJohannna Rothmanさん、Manage It! 現場開発者のための達人式プロジェクトマネジメントの作者さんですね。

開発者が行う改善は55%だが、マネージャーは65%の改善に貢献出来る。目的を持って人をまとめるのがマネージャーの仕事、開発に集中出来る椅子とかを揃える以外にに良い人間関係を築くことが大事。

効率的なマネージメントのやり方を17の法則としてまとめた。以下原文ママ。

  1. Know What They Pay You Do
  2. Plan the Work: Portfolio Management
  3. Accept Only One #1 Priority at at Tme
  4. Commit to Projects After Asking Your Staff
  5. Hire the Best People for the Job
  6. Preserve Good Teams
  7. Avoid Micromanaging or Inflicting Help
  8. Treat People Individually and With Respect
  9. Meet Weekly with Each Person
  10. Plan Training Time in the Workweek (Plan Training Time Each Week for Yourself)
  11. Give Credit Freely
  12. Fire People Who Can’t Do the Work
  13. Emphasize Results, Not Time
  14. Admit Your Mistakes
  15. Recognize and Reward Good Work
  16. Take a Vacation
  17. Manage Yourself

以下Rothmanさんの発言メモ、一部意訳があるかも。

1. 業務上の肩書きと実際の職務内容、使命があっているか確認すること。
3. 優先度1のタスクは常に1つしか無いはず。複数あるのは何かがおかしい予兆。
4. タスクはチームで決めよう。
5. 雇うべきはgreatな人材、それは必ずしもチームに今いる人材とは違う。タイプ(性格/個性)の異なる人を集め、アイデアを生む。
6. 良いチームは残そう、解散するとチームが備えていた力が失われる。
9. 信頼できる関係を築くなら1対1がいい。直接のフィードバックもし易い。
13. 作業時間に比例して作業内容も増える。1週間40時間で仕事を終えられるよう作業を組むのもマネージャーの仕事。

Pragmatic Programmerシリーズの1冊を書いているだけあって実用的で、口先だけの話をしている人ではないのだなと聞いていて感じました。

ソフトウェアアーキテクトが知るべき97のこと

1月 30th, 2010 by tune No comments »
ソフトウェアアーキテクトが知るべき97のこと
オライリージャパン
売り上げランキング: 6647

この本の正しい使い方。

  1. ソフトウェアアーキテクチャに興味を持った人が数人集まる。
  2. 適当に1章選んでみんなで読む
  3. 理解できる/理解できない/何が言いたいのか分からない/昔こんなことがあったなど議論を交わす。
  4. 飽きたら辞める。

97個も話があると似たような話があります。もうちょっと整理してくれたら30個ぐらいにできたのに。
息抜きに読むとたまにヒントが得られる本だと思います。もっと砕けた感じが良ければアドレナリンジャンキーがおすすめです。

・・・

以下は自分が良いなと思ったエッセイです。
◯03 最大の問題は、多分技術的なことではない
相手を人として尊重し、憶測で非難しないこと。話しあうこと

◯08 すべてのものは、かならずエラーを起こす
エラーの影響を緩和するために何かを導入する度に、それが新しいエラーを増やしていく。

◯18 一般性よりも単純性、再利用よりもまず最初に使えること
推測による汎用性よりも、経験を通じた単純性の方が役に立つ。
単に汎用的であることを目標として設計された多くのものは、良く考えられていても何の役にも立たない。

◯37 ソフトウェア・アーキテクチャが倫理的な意味を持つことを考えよ
必須フィールドは特に害が無いように見えるかもしれないけど、設計者の都合をユーザに押し付けてしまっている。
設計者が楽をするためにわずかずつであっても他人の生活を不便にすることは倫理的ではない。

◯54 あなたの知識と経験を共有しよう
経験は1つだけど、そこから出来るだけ大きな知恵を引き出すためには経験に合理的な説明を加えなければならない。
簡単に説明出来るようになるまでは、対象を完全に理解しているとは言えない。

◯61 データがすべて
データはコードよりも概念として小さく、複雑度もかなり低い。

◯72 優れたコンテンツは優れたシステムを作る
新しくシステムを設計するときには、開発プロセスの一部を既存コンテンツの評価に当てるべき。

◯82 本当の顧客は目の前の顧客ではない
本当の顧客はあなたの顧客の顧客。
あなたの顧客の顧客が成功すれば、あなたの顧客が成功する。そうすればあなたも成功する。

◯日06 手段的な技術と陳腐化しない本質的な技術
ノウハウ的な知識ばかりが増えても背景にある理論を理解しないと作れないソフトが有る。
作業の90%はノウハウの積み重ねでソフトウェアの魅力が高められる。しかし残り10%で本質的な知識が要求される。そしてそこでソフトウェアの革新性が決定される。

Linuxで一定時間後にプログラムを起動する

1月 27th, 2010 by tune No comments »

複数のプログラムを同時に動かしても互いに干渉しないなんて今時当たり前ですが、添付ファイルを一時的に用いるプログラムでデータ取りする作業があって、添付ファイルの書き出しで競合が生じる問題に悩まされました。10000枚ぐらい画像を一度に処理するので8時間ぐらいかかってしまいます。

「今日はもう帰りたいんだけど、あと1時間ぐらいしたらデータ取りが終わるから1時間半後にこのプログラム回しておきたいんだけど」というニッチな悩みをしていたところ、Linuxで一定時間後にプログラムを起動する方法を見つけました。
一定の時間後にプログラムを実行するには

例えば1分後にprocess_dataコマンドを実行するなら

% sleep 60; ./process_data

とやっておけばいいそうです。sleepコマンドを使うとターミナルの応答が返ってこなくなりますが、GNU screenと合わせれば問題なしですね。

さらにatコマンドを使って指定時間にプログラムを起動する技もあるそうです。

% at now + 1 hour
at> ls
at> date
at> ([Ctrl]+[D]キーを押す)
warning: commands will be executed using /bin/sh
job 8 at 2001-02-09 14:38

探せば便利な技があるんですね。

0さい~4さいこどもずかん

1月 26th, 2010 by tune No comments »
0さい~4さいこどもずかん 英語つき
デイブ テルキ
学習研究社
売り上げランキング: 3200

本が好きな娘のために購入しました。

たまたま時間つぶしに入った本屋で見つけた本ですが、いろいろな絵が可愛く書いてあり、大人が子供と一緒に眺めるのも楽しいと思います。装丁も頑丈で、ページも耳がついているため、子どもでもめくりやすくなっています。片仮名での英語の発音表記はなくても良い気がしますが、この辺は人それぞれなんでしょうか。

全4巻らしいので、飽きたタイミングを見計らって少しずつ買い増そうかと思っています。

フレーベル館に行ってきました

1月 26th, 2010 by tune No comments »

先週末の話ですが、妻に買い物を頼まれてフレーベル館に行ってきました。アンパンマンで有名なフレーベル館ですね。まだうちの娘はアンパンマンにはまる年齢ではないのですが、最近シールに凝っていて、ごほうびシールにここでしか売ってないキラキラアンパンマンシールがいいとのことでお使いにいってきた次第です。

アンパンマンミュージアムの方が品揃えはすごいのかもしれませんが、隠れ家的な店内はところ狭しとこどものおもちゃが並べられていてなかなか良いお店だなと思いました。お店の目の前は六義園なので、もう少し暖かくなってきたら家族連れで行くのも良いかもしれません。

お店の中にはおむつがえコーナーや、赤ちゃん休憩スペースもあった気がします。次は我が家も子連れで行ってきます。

構成管理手段が作業手順を定義している

1月 14th, 2010 by tune No comments »

今更な話なんですが・・・

ソフトウェアの構成管理をするのは今時当たり前ですが、構成管理システム(バージョン管理システム)の使い方は千差万別です。今でもローカルフォルダに置いてあるとか、ネットワーク上の共有フォルダに置いてあるとか、外注先のローカルフォルダに置いてあるとか、ひどい例を探していくといくらでも考えられます。うちの一昨年の新人曰く「フォルダを作ってフルバージョンを残しておくこと」なんて新人犬種で教わってきたらしいので、ひどい世の中です。

新しい順に分類すると

  • 分散型バージョン管理:Git / Mercurial / Bazaar
  • 集中型バージョン管理:Subversion / Perforce
  • 集中型の旧世代:CVS / Visual Source Safe
  • 古代:フォルダを分ける、共有フォルダに置くとか。

といった形でしょうか。

そして、どうしていつまでも古いやり方を踏襲する人がいるのかという話です。勉強する時間が無いとか、やり方が分からないとか、組織で決められているとかいろいろ理由があるとおもうのですが、「使っている構成管理ツールにあわせて作業手順を決めているから、より優れたツールがもたらすメリットを説明されても何を問題としているのかわからない」という発想がふと浮かびました。

フォルダ管理の人は、一人でしか開発してないから複数人で共有する時の話をしてもピンとこない。もしくは構成管理も含めて外注しているからたまに来る納品物を共有フォルダに置いておくだけで十分なんでしょう。

CVSの人はソフトウェアのバージョンは1.X.Yみたいに増えていくものと信じ込んでいて、複数ファイルをまとめて管理するなんて発想はないんでしょう。VSSの人はファイルをいじるときは一人が長期間ロックするものだという前提があるんでしょう。

Subversionの人はブランチは大きな機能を追加するときにたまに使うものだと思ってるんでしょう。

構成管理ツールと言うのは単に機能を提供するだけではなくて、ソフトウェアの手順を暗黙的に決めてしまいます。逆に考えると、新しいツールを使うときは新しいやり方を最大限活かせるように作業手順を作りなおさないとダメでしょうね。

入門Gitを読んでいて感じたことが、ようやく自分の中で咀嚼できた気がします。

TortoiseSVNのオーバーレイアイコンが表示されないとき

1月 10th, 2010 by tune No comments »

TortoiseSVNだけじゃなくてTortoiseCVS/TortoiseHg/TortoiseGitでも同じだと思います。オーバーレイアイコンが表示されない原因はアイコンキャッシュが壊れていたりといろいろ原因があるのですが、ついこの前気づきにくい理由で表示されないことがあったので参考までに紹介しておきます。

会社の作業環境ではTortoiseSVNとTortoiseGitをインストールしていたのですが、いつからか両方のオーバーレイが表示されなくなってしまいました。てっきり両者が競合でもしてるか、TortoiseGitが悪さでもしているのだろうと思っていたのですが、調べてみるとWindowsの仕様で表示されなくなっていました。

Windowsではオーバーレイさせるアイコンをレジストリで記憶していますが、最大で15個という制限があるそうです。それ以上もレジストリに登録できるのですが、最初に登録されたものから無効になってしまうそうです。自分の場合、あとからインストールしたOffice2010(Microsoft Ofiice Groove?)が原因だったようです。

対処法としてはレジストリをチェックして15個以上登録されてないか確認し、不要なものをアンインストールするか、レジストリの不要項目を削除すればOKです。チェックするレジストリは”HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows
\CurrentVersion\Explorer\ShellIconOverlayIdentifiers”です。

以下のブログを参考にさせていただきました。